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

看板Grad-ProbAsk作者bigrat2 (MrEric)時間16年前 (2010/01/13 00:17)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串3/4 (看更多)

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

01/13 00:24, , 1^F

01/13 00:24, 1^F

→

assassin88

01/13 00:24, , 2^F

01/13 00:24, 2^F

推

killerjoe

01/13 00:25, , 3^F

01/13 00:25, 3^F