[理工] 鴿籠

看板Grad-ProbAsk作者時間4年前 (2019/10/19 10:04), 4年前編輯推噓2(2推 0噓 20→)
留言22則, 4人參與, 4年前最新討論串2/2 (看更多)
http://i.imgur.com/xXdZdi6.jpg
想問這題，一開始A的基數小於等於3就不懂了 ----- Sent from JPTT on my Samsung SM-A730F. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.76.5.42 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1571450688.A.A44.html ※ 編輯: shinle14 (42.76.5.42 臺灣), 10/19/2019 10:05:30
→
10/19 11:01, 4年前 , 1F
因為4以上鴿籠不成立
10/19 11:01, 1F
→
10/19 11:05, 4年前 , 2F
證明3以下必定有相同元素和就等於不是所有非空子集都
10/19 11:05, 2F
→
10/19 11:05, 4年前 , 3F
有唯一元素和
10/19 11:05, 3F
→
10/19 11:07, 4年前 , 4F
3以下就只有{ 1 } ~ { 7, 8, 9 } 最多24個sum
10/19 11:07, 4F
→
10/19 11:07, 4年前 , 5F
但有25種subset
10/19 11:07, 5F
推
10/19 11:10, 4年前 , 6F
先了解題目在幹嘛 每個非空子集合都會有一個元素和
10/19 11:10, 6F
→
10/19 11:10, 4年前 , 7F
元素和的值域落在(1+2+3+4+5)~(9+8+7+6+5)
10/19 11:10, 7F
→
10/19 11:10, 4年前 , 8F
把非空子集合的個數想像成鴿子，元素和值域想成籠子
10/19 11:10, 8F
→
10/19 11:10, 4年前 , 9F
那只要證明值域的範圍小於非空子集合個數(31)
10/19 11:10, 9F
→
10/19 11:10, 4年前 , 10F
就可以用鴿籠證明一定有兩個非空子集合元素和一樣
10/19 11:10, 10F
→
10/19 11:10, 4年前 , 11F
詳解的證法樓上講的很清楚了 就不贅述
10/19 11:10, 11F
→
10/19 11:10, 4年前 , 12F
不過其實也不是4以上不成立啦
10/19 11:10, 12F
→
10/19 11:10, 4年前 , 13F
也能直接用5個元素的情況來證 只是會麻煩一點
10/19 11:10, 13F
推
10/19 12:51, 4年前 , 14F
10/19 12:51, 14F
→
10/19 12:51, 4年前 , 15F
類似題，但籠>鴿直接鴿籠不一定會保證兩個一樣
10/19 12:51, 15F
→
10/19 12:51, 4年前 , 16F
A<=6(藍色)要找兩個一樣但沒辦法保證找到，我們縮小範圍
10/19 12:51, 16F
→
10/19 12:51, 4年前 , 17F
去A<=5(紅色)找，如果找得到代表藍色也有兩個一樣
10/19 12:51, 17F
→
10/19 12:52, 4年前 , 18F
你這題就是A<=5找不到去A<=4找還是找不到就去A<=3
10/19 12:52, 18F
→
10/19 14:34, 4年前 , 19F
謝謝各位，我研究一下
10/19 14:34, 19F
→
10/20 00:07, 4年前 , 20F
熊熊發現上面打錯...
10/20 00:07, 20F
→
10/20 00:07, 4年前 , 21F
子集合的元素合值域是落在1~(9+8+7+6+5)才對...
10/20 00:07, 21F
→
10/20 00:07, 4年前 , 22F
有誤導的話非常抱歉qq
10/20 00:07, 22F
哈哈我有猶豫一下，還是謝謝mi大大～～ ※ 編輯: shinle14 (42.76.106.117 臺灣), 10/20/2019 10:44:27
‣ 更多 shinle14 的文章
文章代碼(AID): #1Tgcz0f4 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
0
6
[理工] 鴿籠 鴿籠
shinle14
4年前, 09/09
理工
2
22
[理工] 鴿籠 鴿籠
shinle14
4年前, 10/19
在新視窗開啟完整討論串 (共2篇)
‣ 更多 shinle14 的文章
文章代碼(AID): #1Tgcz0f4 (Grad-ProbAsk)