作者CYCUStore (中原大学店)
看板Grad-ProbAsk
标题[理工] 108中山离散鸽笼?
时间Sat Feb 2 19:34:18 2019
忘记题号惹
题目:
一个集合S有5个正整数，最大不超过9，证明S的所有子集合(不包含空集合)
的元素和(sum of elements)不会都不同
想问一下这题要怎麽解，是用鸽笼原理吗?
原本是想说S的非空子集合有2^5 - 1 = 31个
然後从5个数最小1~最大1+6+7+8+9 可是这个还是31个数 不知怎麽算
求大大们开释
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.231.173.2
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549107260.A.C0C.html
1F：推 Dora5566: 居然考这种基本题@@ 02/02 19:35
算不出来 惨了..
2F：推 sdfg014025xx: 我用矛盾证法 但我觉得证的很不严谨... 02/02 19:36
3F：推 qqgnoe466263: 我怎麽想也都是笼子大於鸽子，求神人解答 02/02 19:37
4F：推 h3882249: 每数都不同，size1，2，3的子集合有25个 02/02 19:43
5F：推 sooge: 我直接把31的状况全列出来然後再说6+9=7+8 02/02 19:44
6F：→ h3882249: 子集合和范围在1-25(9+8+7)? 02/02 19:44
7F：→ h3882249: 说错1-24 02/02 19:45
8F：→ sooge: 然後又因为31已经是极端值了 所以直接得证任选五个数的合 02/02 19:45
9F：→ sooge: 必会重复 02/02 19:45
11F：→ moozkito: 刚刚翻课本 是这种题目吧? 02/02 19:46
懂了...原来课本就有 感谢各位大大
12F：推 h3882249: 看起来是这样，当下写发现大小1，2，3的所有子集合数就 02/02 19:50
13F：→ h3882249: 大於他们的范围了 02/02 19:50
14F：推 ChunagMT: 话说为什麽是1+6+7+8+9 02/02 19:56
想说要凑最小数一定要1 其他就最大数凑最大范围
其实一开始是用1~5+6+7+8+9 可是大太多了...
※ 编辑: CYCUStore (36.231.173.2), 02/02/2019 20:04:34
15F：→ sooge: 56789值域范围也是31个数 5~35 02/02 20:05
16F：→ sooge: 16789 26789 36789 46789 56789同理 02/02 20:07
17F：→ sooge: 所以解决这五个 这题鸽笼应该就解决了 不知道我有没有露了 02/02 20:08
18F：→ sooge: 什麽 02/02 20:08
20F：→ albertnien: 只有证|S|=5不知道对不对 02/02 20:45
21F：→ DLHZ: 考虑数字越大越好(和不会在限制内减少选项)有两个限制1.选到 02/02 20:47
22F：→ DLHZ: 的数同样的差不能出现3次2.选的数不能为现有的差的和 所以从 02/02 20:47
23F：→ DLHZ: 9,8,7开始 这时候选项只剩下{5,4,3}但要选两个 一定会选到一 02/02 20:47
24F：→ DLHZ: 个数使得选出来的数列不符合限制 大概是这样 详细的太长了 02/02 20:47
25F：推 skyHuan: 越小越好吧 小的找得到大的一定找得到 02/02 21:40
26F：推 meokay: 这题应该是2^5-1=31 然後无论最小元素和结合的取法或最大 02/02 21:50
27F：→ meokay: 元素和集合的取法 他们的Power set下的各个子集合的范围 02/02 21:50
28F：→ meokay: 都会小於31 再根据鸽笼就可以了 02/02 21:50
29F：→ meokay: 集合 不是 结合 打错 02/02 21:51
32F：→ rockieloser: 这方法真棒 哈哈 倒是没想到 02/02 22:22
33F：推 ruifan: 大概是课本题目 因为题目的说法是只要有任何一组subset su 02/02 22:22
34F：→ ruifan: m相同就好 所以可以缩小取的subset大小 然後就用鸽笼了 02/02 22:22
35F：→ rockieloser: 看到才想起自己看过 倒是忘的乾净 02/02 22:24
36F：推 nannnnn: 我是分开讨论欸 讨论最大是9跟最大是8以下如果最大是8值 02/02 22:30
37F：→ nannnnn: 域一定要小於27如果最大是9则5＋6＋7＋8＋1一定不在值域 02/02 22:30
38F：→ nannnnn: 里面所以也是小於30 02/02 22:30
39F：推 Dora5566: 看不懂楼上最大是9後面那句 02/02 22:41
40F：→ ERT312: 最大是9，值可能有5+6+7+9呀 02/02 22:44
41F：→ ERT312: 是可以分组讨论:若{6,7,8,9}不是S的子集，sum的范围是 02/02 22:48
42F：→ ERT312: m≦sum < m+6+7+8+9，长度小於31可以直接套鸽笼了 02/02 22:49
43F：→ ERT312: m是S中的最小元素 02/02 22:50
44F：→ ERT312: 若{6,7,8,9}是S的子集，也很容易在m~m+30中剃除一个值 02/02 22:51
45F：推 nannnnn: 当初是写1＋6＋7＋8＋1拉说错了不过我是用广义的a b c d 02/02 22:54
46F：→ nannnnn: 四个元素 但我好像真的没考虑到5678看来是错了QQ 02/02 22:54
47F：推 Dora5566: 要怎麽剃除一个值 02/02 22:56
48F：→ ERT312: 举例若S={1,6,7,8,9}，则sum不会有 2,3,4,5 02/02 22:58
49F：→ ERT312: 若S={5,6,7,8,9}，sum不会有10 02/02 22:59
50F：→ nannnnn: 早知道9还不如给他爆开8以下再用鸽笼就好 02/02 23:00
51F：→ q79236: 爆开了 -12 02/02 23:12
52F：推 yunghan15: 靠北我忘记我不小心把鸽子跟笼子想返还证得沾沾自喜想 02/03 09:39
53F：→ yunghan15: 说好开心不需要证到第二步把范围缩小== 02/03 09:40