每日一题[1658]转圈圈

设 $A$ 是一个含有 $n$ 个元素的集合，$A_{1},A_{2},\cdots,A_{n}$ 是 $A$ 的互不相同的 $n$ 个子集．证明：在 $A$ 中存在一个元素 $a$，使得 $A_{1}-\{a\},A_{2}-\{a\},\cdots,A_{n}-\{a\}$ 仍是互不相同的集合，其中 $A_{i}-\{a\}=\{x\in A_{i}\mid x\ne a\}$．

解析    用反证法．假设命题不成立，则对任何 $a\in A,A_{1}-\{a\},A_{2}-\{a\},\cdots,A_{n}-\{a\}$ 中必有两个集合相同．我们构造一个图 $G$，其顶点标记为 $A_{1},A_{2},\cdots,A_{n}$，且 $A_{i}$ 与 $A_{j},1\leqslant 1\leqslant i\ne j \leqslant n$ 连一条（标记为 $a$），如果 $A_{i}-\{a\}=A_{j}-\{a\}$．我们将图 $G$ 中具有相同标号的边只保留一条（多余的去掉），则我们得到一个图 $G'$，它含有 $n$ 个点，$n$ 条边，且每条边的标号不同，易见 $G'$ 含有一个圈，记为

$$C=A_{i_{1}}A_{i_{2}}\cdots A_{i_{r}}A_{i_{1}},r\geqslant 3.$$ 一方面，$A_{i_{1}}$ 到 $A_{i_{2}}$，再到 $A_{i_{3}},\cdots ,A_{i_{r}}$，最后回到 $A_{i_{1}}$ 增减的元素是互不相同的，另一方面，从 $A_{i_{1}}$ 出发增减元素后返回到 $A_{i_{1}}$ 却是一个相同的集合，矛盾．因此原命题得证．