忘记题号惹
题目:
一个集合S有5个正整数，最大不超过9，证明S的所有子集合(不包含空集合)
的元素和(sum of elements)不会都不同
想问一下这题要怎么解，是用鸽笼原理吗?
原本是想说S的非空子集合有2^5 - 1 = 31个
然后从5个数最小1~最大1+6+7+8+9 可是这个还是31个数 不知怎么算
求大大们开释
作者: qqgnoe466263 (Yen) 2019-02-02 19:37:00
我怎么想也都是笼子大于鸽子，求神人解答
作者:
sooge (老衲)
2019-02-02 19:44:00我直接把31的状况全列出来然后再说6+9=7+8
子集合和范围在1-25(9+8+7)?说错1-24
作者:
sooge (老衲)
2019-02-02 19:45:00然后又因为31已经是极端值了 所以直接得证任选五个数的合必会重复
作者: moozkito (Once!) 2019-02-02 19:46:00
看起来是这样，当下写发现大小1，2，3的所有子集合数就大于他们的范围了
作者: ChunagMT (muting) 2019-02-02 19:56:00
话说为什么是1+6+7+8+9
作者:
sooge (老衲)
2019-02-02 20:05:0056789值域范围也是31个数 5~3516789 26789 36789 46789 56789同理所以解决这五个 这题鸽笼应该就解决了 不知道我有没有露了什么
作者: albertnien 2019-02-02 20:44:00
作者:
DLHZ ( )
2019-02-02 20:47:00考虑数字越大越好(和不会在限制内减少选项)有两个限制1.选到的数同样的差不能出现3次2.选的数不能为现有的差的和 所以从9,8,7开始 这时候选项只剩下{5,4,3}但要选两个 一定会选到一个数使得选出来的数列不符合限制 大概是这样 详细的太长了
作者:
skyHuan (Huan)
2019-02-02 21:40:00越小越好吧 小的找得到大的一定找得到
作者:
meokay (我可以)
2019-02-02 21:50:00这题应该是2^5-1=31 然后无论最小元素和结合的取法或最大元素和集合的取法 他们的Power set下的各个子集合的范围都会小于31 再根据鸽笼就可以了集合 不是 结合 打错
作者:
skyHuan (Huan)
2019-02-02 22:00:00作者:
ruifan (我是瑞凡)
2019-02-02 22:16:00作者:
ruifan (我是瑞凡)
2019-02-02 22:22:00大概是课本题目 因为题目的说法是只要有任何一组subset sum相同就好 所以可以缩小取的subset大小 然后就用鸽笼了
作者: nannnnn (nannnnn) 2019-02-02 22:30:00
我是分开讨论欸 讨论最大是9跟最大是8以下如果最大是8值域一定要小于27如果最大是9则5＋6＋7＋8＋1一定不在值域里面所以也是小于30
作者:
ERT312 (312)
2019-02-02 22:44:00最大是9，值可能有5+6+7+9呀是可以分组讨论:若{6,7,8,9}不是S的子集，sum的范围是m≦sum < m+6+7+8+9，长度小于31可以直接套鸽笼了m是S中的最小元素若{6,7,8,9}是S的子集，也很容易在m~m+30中剃除一个值
作者: nannnnn (nannnnn) 2019-02-02 22:54:00
当初是写1＋6＋7＋8＋1拉说错了不过我是用广义的a b c d四个元素 但我好像真的没考虑到5678看来是错了QQ
作者:
ERT312 (312)
2019-02-02 22:58:00举例若S={1,6,7,8,9}，则sum不会有 2,3,4,5若S={5,6,7,8,9}，sum不会有10
作者: nannnnn (nannnnn) 2019-02-02 23:00:00
早知道9还不如给他爆开8以下再用鸽笼就好
作者:
q79236 (昕翔)
2019-02-02 23:12:00爆开了 -12
靠北我忘记我不小心把鸽子跟笼子想返还証得沾沾自喜想说好开心不需要証到第二步把范围缩小==