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