i****1
发帖数: 445 | 1 哪位将军能做出来？
证明:
从1到99中任取10个不同的数组成集合X,X
中必存在两个不相交的真子集Y和Z,使得Y
的元素之和与Z的元素之和相等。 | w****n
发帖数: 113 | 2 10个不同的数可构成2^10=1024个不同的和式。1-99里10(or fewer)个数的和小于1000,
由pigeon hole principle，必有两个不同和式share相同的和。Cancel out共同的
summands (if any),得到两个和相同的不相交真子集。 | d**s
发帖数: 4741 | 3 漂亮
1000,
【在 w****n 的大作中提到】
: 10个不同的数可构成2^10=1024个不同的和式。1-99里10(or fewer)个数的和小于1000,
: 由pigeon hole principle，必有两个不同和式share相同的和。Cancel out共同的
: summands (if any),得到两个和相同的不相交真子集。
| i****1
发帖数: 445 | 4 牛。
我开始的思路是先找不相交真子集，再看和是否相等，这样走进了死胡同。
你这个思路，一开始就用pigeonhole principle，然后去掉相同元素，就是不相交真子
集了。
p.s. 顺便问下大神，一个集合的不相交真子集可以找出来吗？
1000,
【在 w****n 的大作中提到】
: 10个不同的数可构成2^10=1024个不同的和式。1-99里10(or fewer)个数的和小于1000,
: 由pigeon hole principle，必有两个不同和式share相同的和。Cancel out共同的
: summands (if any),得到两个和相同的不相交真子集。
|
|
