设 $n$ 为 正 整数，集合 $A_{1}, A_{2}, \cdots, A_{n+1}$ 是 集 合 $\{1,2, \cdots, n\}$ 的 $n + 1$ 个非空子集．证明：存 在 $\{1,2, \cdots, n+1\}$ 的两个不交的非空子集 $\left\{i_{1}, i_{2}, \cdots, i_{k}\right\}$ 和 $\{ j_{1}, j_{2}, \cdots, j_{m} \}$，使得 $A_{i_{1}} \bigcup A_{i_{2}} \bigcup \cdots \bigcup A_{i_{k}}=A_{j_{1}} \bigcup A_{j_{2}} \bigcup \cdots \bigcup A_{j_{n}}$．
【难度】
【出处】
2002年中国西部数学奥林匹克试题
【标注】
【答案】
略
【解析】
对 $n$ 归纳，用数学归纳法证明．
当 $n=1$ 时，必有 $A_{1}=A_{2}=\{1\}$，命题获证．
设命题对 $n=l$ 成立，考虑 $n=l+1$ 的情形．
此时若存在 $A_{i}=A_{j}$，则命题成立．因此，可设 $A_{1}, A_{2}, \cdots, A_{l+2}$ 两两不同．令 $A_{i}^{\prime}=A_{i} \backslash\{l+1\}$，则 $A_{i}^{\prime} \subseteq\{1,2, \cdots, l\}, i=1,2, \cdots, l+2$．
（1）$A_{i}^{\prime}$ 两两不同．此时，考虑 $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{l+1}^{\prime}$，运用归纳假设，可得分组 $U_{1}^{\prime}\overset{记}{=}A_{i_1}^{\prime} \cup A_{i_2}^{\prime} \cup \cdots \cup A_{i_3}^{\prime}=A_{j_{1}}^{\prime} \cup A_{j_{2}}^{\prime} \cup \cdots \cup A_{j_{l}}^{\prime}\overset{记}{=}U_{2}^{\prime}$ ①
如果将式 ① 中的 $A^\prime_i$ 改为 $A_i$ 后，得 $U_{1}=U_{2}$，则命题获证．若 $U_{1} \neq U_{2}$，则必有一边含有 $l+1$，而另一边不含 $l+1$，不妨设 $l+1 \in A_{i_{1}}$．而对任意 $1 \leqslant k \leqslant t$，均有 $l+1 \notin A_{j_{k}}$．
此时，考虑 $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{l+2}^{\prime}$ 中除 $A_{i_{1}}^{\prime}$ 以外的 $l+1$ 个集合．利用归纳假设，可得另一分组
$U_{3}^{\prime}\overset{记}{=}A_{\overline{i}_{1}}^{\prime} \cup A_{\overline{i}_{2}}^{\prime} \cup \cdots \cup A_{\overline{i}_{u}}^{\prime}=A_{\overline{j}_{1}}^{\prime} \cup A_{\overline{j}_{2}}^{\prime} \cup \cdots \cup A_{\overline{j}_{u}}^{\prime}\overset{记}{=}U^\prime_{4}$ ②
如果将式 ② 中的 $A_{i}^{\prime}$ 改为 $A_j$ 后，得 $U_{3}=U_{4}$，则命题获证．若 $U_3\ne U_4$，则必有另一边含有 $l+1$，而另一边不含 $l+1$，不妨设 $l+1 \notin U_{3}, l+1 \in U_{4}$．此时，考虑下面的并集 $U^{\prime}_{1} \cup U_{3}^{\prime}=U_{2}^{\prime} \cup U^{\prime}_{4}$ ③
则式 ③ 中两边去掉" $\prime$ "后，必有 $U_{1} \cup U_{3}=U_{2} \cup U_{4}$．这时，只需对式 ③ 中下标相同的集合予以处理．
注意到，$A_{i_{1}}^{\prime} \in U_{1}$，但 $A_{i_{1}}^{\prime} \notin U_{k}, k=2,3,4$，故下标 $i_1$ 仅在式 ③ 中出现一次．从而，在将下标相同的集合去掉时（保持式 ③ 成立），式 ③ 的两边不会变为空集．若 ${A}_{i}^{\prime}$ 在式 ③ 中重复出现，不妨设 ${A}_{i}^{\prime} \in {U}_{1}^{\prime}$，若 ${A}_{i}^{\prime} \in {U}_{3}^{\prime}$，则从 $U_{3}^\prime $ 中去掉 $ {A}_{i}^{\prime}$，式 ③ 仍成立；若 $A_{i}^{\prime} \in U_{2}^{\prime} \bigcup U_{4}^\prime$，由于 $U_{1}^{\prime}$ 与 $U_{2}^{\prime}$ 的下标不同，故必有 $A_{i}^{\prime} \in U_{4}^\prime$．此时结合 $U_{1}^{\prime}=U_{2}^{\prime}$ 可知，将 ${A}_{i}^{\prime}$ 从 ${U}_{4}^\prime$ 中去掉后，式 ③ 仍成立．一次处理，直至式 ③ 两边没有相同下标的项，从而命题获证．
（2）若 ${A}_{i}^{\prime}$ 中存在相同的集合 $(1 \leqslant i \leqslant l+2)$，这时，如果 $\boldsymbol{A}_{i}^{\prime}$ 中有 $3$ 个相同，不妨设 $A_{1}^{\prime}=A_{2}^{\prime}=A_{3}^{\prime}$，则 $A_{1}, A_{2}, A_{3}$ 中必有 $2$ 个相等，矛盾；如果 $\boldsymbol{A}_{\mathbf{i}}^{\prime}$ 中有两对集合分别相等．不妨设 $A_{1}^{\prime}=A_{2}^{\prime}, A_{3}^{\prime}=A_{4}^{\prime}$，这时 $A_{1} , A_{2}$ 中恰有一个含有 $l+1$，$ A_{3}, A_{4}$ 中也恰有一个含有 $l+1$．不妨设 $l+1 \in A_{1}, l+1 \in A_{3}$，而 $l+1 \notin A_{2}, l+1\notin A_4$，此时，得到 $A_{1} \cup A_{4}=A_{2} \cup A_{3}$．命题获证．
最后，$A_{i}^{\prime}$ 中恰有两个集合相同，设为 $A_{1}^{\prime}=A_{2}^{\prime}$，此时，$l+1$ 必恰属于 $A_{1} ,A_{2}$ 中的一个．注意到，两个集合组 $A_{1}^{\prime}, A_{3}^{\prime}, \cdots, A_{l+2}^{\prime}$ 与 $A_{2}^{\prime}, A_{3}^{\prime}, \cdots, A_{l+2}^{\prime}$ 中没有相同的集合（指同一组内）．这时，利用（1）的处理方法，可知命题成立．
综上可知，命题对一切正整数 $n$ 成立．
当 $n=1$ 时，必有 $A_{1}=A_{2}=\{1\}$，命题获证．
设命题对 $n=l$ 成立，考虑 $n=l+1$ 的情形．
此时若存在 $A_{i}=A_{j}$，则命题成立．因此，可设 $A_{1}, A_{2}, \cdots, A_{l+2}$ 两两不同．令 $A_{i}^{\prime}=A_{i} \backslash\{l+1\}$，则 $A_{i}^{\prime} \subseteq\{1,2, \cdots, l\}, i=1,2, \cdots, l+2$．
（1）$A_{i}^{\prime}$ 两两不同．此时，考虑 $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{l+1}^{\prime}$，运用归纳假设，可得分组 $U_{1}^{\prime}\overset{记}{=}A_{i_1}^{\prime} \cup A_{i_2}^{\prime} \cup \cdots \cup A_{i_3}^{\prime}=A_{j_{1}}^{\prime} \cup A_{j_{2}}^{\prime} \cup \cdots \cup A_{j_{l}}^{\prime}\overset{记}{=}U_{2}^{\prime}$ ①
如果将式 ① 中的 $A^\prime_i$ 改为 $A_i$ 后，得 $U_{1}=U_{2}$，则命题获证．若 $U_{1} \neq U_{2}$，则必有一边含有 $l+1$，而另一边不含 $l+1$，不妨设 $l+1 \in A_{i_{1}}$．而对任意 $1 \leqslant k \leqslant t$，均有 $l+1 \notin A_{j_{k}}$．
此时，考虑 $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{l+2}^{\prime}$ 中除 $A_{i_{1}}^{\prime}$ 以外的 $l+1$ 个集合．利用归纳假设，可得另一分组
$U_{3}^{\prime}\overset{记}{=}A_{\overline{i}_{1}}^{\prime} \cup A_{\overline{i}_{2}}^{\prime} \cup \cdots \cup A_{\overline{i}_{u}}^{\prime}=A_{\overline{j}_{1}}^{\prime} \cup A_{\overline{j}_{2}}^{\prime} \cup \cdots \cup A_{\overline{j}_{u}}^{\prime}\overset{记}{=}U^\prime_{4}$ ②
如果将式 ② 中的 $A_{i}^{\prime}$ 改为 $A_j$ 后，得 $U_{3}=U_{4}$，则命题获证．若 $U_3\ne U_4$，则必有另一边含有 $l+1$，而另一边不含 $l+1$，不妨设 $l+1 \notin U_{3}, l+1 \in U_{4}$．此时，考虑下面的并集 $U^{\prime}_{1} \cup U_{3}^{\prime}=U_{2}^{\prime} \cup U^{\prime}_{4}$ ③
则式 ③ 中两边去掉" $\prime$ "后，必有 $U_{1} \cup U_{3}=U_{2} \cup U_{4}$．这时，只需对式 ③ 中下标相同的集合予以处理．
注意到，$A_{i_{1}}^{\prime} \in U_{1}$，但 $A_{i_{1}}^{\prime} \notin U_{k}, k=2,3,4$，故下标 $i_1$ 仅在式 ③ 中出现一次．从而，在将下标相同的集合去掉时（保持式 ③ 成立），式 ③ 的两边不会变为空集．若 ${A}_{i}^{\prime}$ 在式 ③ 中重复出现，不妨设 ${A}_{i}^{\prime} \in {U}_{1}^{\prime}$，若 ${A}_{i}^{\prime} \in {U}_{3}^{\prime}$，则从 $U_{3}^\prime $ 中去掉 $ {A}_{i}^{\prime}$，式 ③ 仍成立；若 $A_{i}^{\prime} \in U_{2}^{\prime} \bigcup U_{4}^\prime$，由于 $U_{1}^{\prime}$ 与 $U_{2}^{\prime}$ 的下标不同，故必有 $A_{i}^{\prime} \in U_{4}^\prime$．此时结合 $U_{1}^{\prime}=U_{2}^{\prime}$ 可知，将 ${A}_{i}^{\prime}$ 从 ${U}_{4}^\prime$ 中去掉后，式 ③ 仍成立．一次处理，直至式 ③ 两边没有相同下标的项，从而命题获证．
（2）若 ${A}_{i}^{\prime}$ 中存在相同的集合 $(1 \leqslant i \leqslant l+2)$，这时，如果 $\boldsymbol{A}_{i}^{\prime}$ 中有 $3$ 个相同，不妨设 $A_{1}^{\prime}=A_{2}^{\prime}=A_{3}^{\prime}$，则 $A_{1}, A_{2}, A_{3}$ 中必有 $2$ 个相等，矛盾；如果 $\boldsymbol{A}_{\mathbf{i}}^{\prime}$ 中有两对集合分别相等．不妨设 $A_{1}^{\prime}=A_{2}^{\prime}, A_{3}^{\prime}=A_{4}^{\prime}$，这时 $A_{1} , A_{2}$ 中恰有一个含有 $l+1$，$ A_{3}, A_{4}$ 中也恰有一个含有 $l+1$．不妨设 $l+1 \in A_{1}, l+1 \in A_{3}$，而 $l+1 \notin A_{2}, l+1\notin A_4$，此时，得到 $A_{1} \cup A_{4}=A_{2} \cup A_{3}$．命题获证．
最后，$A_{i}^{\prime}$ 中恰有两个集合相同，设为 $A_{1}^{\prime}=A_{2}^{\prime}$，此时，$l+1$ 必恰属于 $A_{1} ,A_{2}$ 中的一个．注意到，两个集合组 $A_{1}^{\prime}, A_{3}^{\prime}, \cdots, A_{l+2}^{\prime}$ 与 $A_{2}^{\prime}, A_{3}^{\prime}, \cdots, A_{l+2}^{\prime}$ 中没有相同的集合（指同一组内）．这时，利用（1）的处理方法，可知命题成立．
综上可知，命题对一切正整数 $n$ 成立．
答案
解析
备注
