[理工] [離散] 鴿籠原理

[bigrat2 (MrEric)]

 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
推 assassin88:因為從|A|=5開始推(鴿子多)一路推到|A|=3才滿足鴿籠
→ assassin88:打錯..(籠子多)
推 killerjoe:你要先去try所有的可能~因為若使用5個元素的和
→ killerjoe:會因為籠子太多而無法利用鴿籠來解
→ killerjoe:五個元素的話是和為5+6+7+8+9=35
推 killerjoe:取法只有2^5=32無法使用鴿籠原理來解
→ bigrat2:瞭解了 謝謝大家 :)