已知一个集合含有10个互不相同的两位数求证：这个集合必有两个无公共元素的子集，这两个子集的各元素之和相等(有用到抽屉原理)

Question

已知一个集合含有10个互不相同的两位数
求证：这个集合必有两个无公共元素的子集，这两个子集的各元素之和相等(有用到抽屉原理)

Answer 1

已知这个集合有1023个不同的非空子集,每一个子集内个数之和都不超过99+98+97+.+90=945《1023.根据抽屉原理,一定存在两个不同的子集,其元素之和相等,删去这两个子集中的共有元素,可得两个无公共元素的非空子集,其所含的各元素之和相等
可以这么理10个元素2^10-1=1023个子集,而数字和只可能在10（最少一个两位数的子集）到99+98+97+.+90=945（最多十个数的子集）之间变动,范围远比1023小,
根据抽屉原理：数字和只有不到945种可能,却有1023个子集的数字和,故必然会存在子集A,B的数字和相等,假设A,B有共同元素,删去这些共同元素,会得到两个新的子集C,D,由于A,B是两个不同子集,那么必然存在不同元素,所以C,D必然不相等,C,D是A,B的子集,那也是原集合的子集,而A,B数字和相等,减去相同元素后数字和当然还相等 ,而此时的子集C,D是两个无公共元素的非空子集,故得证