作者bigrat2 (MrEric)
看板Grad-ProbAsk
標題[理工] [離散] 鴿籠原理
時間Wed Jan 13 00:17:50 2010
Let S be a set of five positive integers the maximum of which is
at most 9 .Prove that the sums of the elements in all the nonempty
subsets of S cannot all be distinct.
解 ： 考慮s中具有 1小於等於|A|小於等於3的子集 A
令A中的元素和為sumA , S中這種子集個數為 C5取1 +C5取2 +C5取3 =25個
sumA滿足1小於等於sumA小於等於 7+8+9=24 ,因為每個子集唯一對應一個元素和
由鴿籠原理知道必有兩個子集具有相同的元素和.
我想請問這一步驟 s中具有 1 小於等於｜A| 小於等於 3 的子集A
是怎麼知道的呢？ 7+8+9又是怎麼推導的呢？
謝謝指點
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.6.216
1F：推 assassin88:因為從|A|=5開始推(鴿子多)一路推到|A|=3才滿足鴿籠 01/13 00:24
2F：→ assassin88:打錯..(籠子多) 01/13 00:24
3F：推 killerjoe:你要先去try所有的可能~因為若使用5個元素的和 01/13 00:25
4F：→ killerjoe:會因為籠子太多而無法利用鴿籠來解 01/13 00:25
5F：→ killerjoe:五個元素的話是和為5+6+7+8+9=35 01/13 00:26
6F：推 killerjoe:取法只有2^5=32無法使用鴿籠原理來解 01/13 00:29
7F：→ bigrat2:瞭解了 謝謝大家 :) 01/13 00:53