Title

现有 $10$ 个人,他们每个人的年龄都是不小于 $1$ 且不大于 $60$ 的正整数,试证:总存在不相交的两组人,使得他们的年龄之和相等.

Proof

由这 $10$ 个人组成的集合共有 $2^{10}-1=1023$ 个非空子集,且这 $10$ 个人的集合的子集的年龄和的范围是 $1-600$,由抽屉原理可知,显然有两个子集的和相等.

若这两个子集不相交,则命题自然成立;

若这两个子集相交,则令它们分别减去相交的部分,则得到的两个作为差的子集(注意:它们必定非空,为何?留作读者思考)显然仍使命题成立.

Q.E.D.

Expansion

若把原题中的 “ $10$ 个人” 改为 “ $9$ 个人”,命题是否仍然成立?

Proof of Expansion

仍然成立.

于是由这 $9$ 个人构成的集合的非空子集数为 $2^9-1=511$,而按照原来的证明思路,这九个人中抽若干位所组成的子集年龄之和的范围是 $1-540$,而 $540>511$,无法继续使用抽屉原理;

然而,注意到:若存在两个人具有相同的年龄,则命题就将自然的成立;

因此,为了避免这种情况,年龄最大的人其年龄不超过 $60$ ,次大的人年龄不超过 $59$……以此类推,他们的年龄范围最大不应该超过 $60+59+\cdots+52=504$ ,而 $511>504$ ,因此根据抽屉原理可知,存在两个子集,其成员的年龄之和相等.

与原来的证明类似,不管这两个子集是否相交,最终都使得命题成立.

Q.E.D.

Note

这一问题难度不大,但稍微值得一提的是,它的加强命题的证明的过程,向我们展示了 “去掉空抽屉(以缩减抽屉数量)” 的技巧, 这一类型的技巧以后会时常遇到.