组合数学证明题对于100以内的任意10个正整数构成的集合,必能找到此集合的两个不相交的子集ab是ab中元素数字和相等

Question

组合数学证明题
对于100以内的任意10个正整数构成的集合,必能找到此集合的两个不相交的子集ab是ab中元素数字和相等

Answer 1

由10个不同数组成的集合,其非空子集数为2^10-1=1023个,
又其元素的值介于1~100.因此其非空子集中元素之和最小为55,最大为191*5.
那么任何两个子集元素和之差的绝对值介于0~900,
考虑其子集的子集对(a,b)(a不等于b).有C(1023,2)=1023*511个.
1023*511显然要比901大得太多,由抽屉原理可知,一定存在一个(可见这里不止一个)子集对(a.b),使得a的元素和与b的元素和之差为0.
记c为子集对(a,b)的交集,c显然严格包含于a,b中(否则推出a与b互相包含.那么a,b元素和之差显然不是0,矛盾.)
那么a-c,与b-c不相交,且a-c与b-c的元素数字和之差恰为0,因此a-c的元素和与b-c的元素和相等.