第1题

证明:从十个互不相同的两位数(十进制)组成的集合中,总能选出两个不相交的子集,使得它们各自元素之和相等。

第 3/4 步：去掉公共部分得到不相交的集合

通俗地说

总重量相同的两堆不同物品,只要每件物品的重量都是正的,就不可能一堆完全包含在另一堆里;因此去掉双方共有的部分后,两边仍各自剩下一些东西。

A'=A\setminus B,\quad B'=B\setminus A

详细分析

设 $A'=A\setminus B$ , $B'=B\setminus A$ 。按构造这两个集合不相交。由于 $S$ 中的元素都是正数, $A\neq B$ 就迫使 $A\not\subseteq B$ 且 $B\not\subseteq A$ (否则两者之和不可能相等,因为在所有元素均为正的情况下,真子集的和必严格小于其超集的和)。因此 $A'$ 与 $B'$ 都非空。