第1题

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

第 2/4 步：运用鸽笼原理

通俗地说

这是经典的鸽笼原理:把比盒子数量更多的物品放进盒子里,就必有一个盒子装了至少两件物品。

1024 > 946 \implies \exists\, A\neq B,\ \text{sum}(A)=\text{sum}(B)

详细分析

由于 $1024$ 个子集(“鸽子”)只对应 $946$ 个可能的和(“鸽笼”),根据鸽笼原理, $S$ 中必存在两个不同的子集 $A\neq B$ 使得 $\text{sum}(A)=\text{sum}(B)$ 。