作者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