给定整数 $n\geqslant 2$．黑板上写着 $n$ 个集合，然后进行如下操作：选取黑板上两个互相不包含的集合 $A,B$，擦掉它们，然后写上 $A\bigcap B$ 和 $A\bigcup B$．这称为一次操作．如此操作下去，直到任意两个集合中都有一个包含另一个为止．对所有的初始状态和操作方式，求操作次数的最大可能值．
【难度】
【出处】
2015第14届CGMO试题
【标注】
【答案】
$C_{n}^{2}=\frac{n(n-1)}{2}$
【解析】
首先我们证明操作次数不可能超过 $C_{n}^{2}=\frac{n(n-1)}{2}$．
当黑板上写着 $n$ 个集合时，考虑成包含关系的集合对的数量，我们证明，每次操作后，这个数量至少增加1．假设我们将 $A,B$ 变成 $A\bigcap B$ 和 $A\bigcup B$．首先 $A,B$ 不是包含关系，而 $A\bigcap B$ 和 $A\bigcup B$ 是包含关系，故这里至少增加了一对成包含关系的集合对．对于另一集合 $C$，若 $C$ 与 $A,B$ 之一成包含关系，由对称性不妨设 $A\subseteq C$，则 $A\bigcap B\subseteq C$，即 $C$ 至少与 $A\bigcap B$ 和 $A\bigcup B$ 之一成包含关系；若 $C$ 与 $A,B$ 均成包含关系，则由 $A,B$ 不成包含关系知或者 $A\subseteq C,B\subseteq C$，或者 $A\supseteq C,B\supseteq C$，若为前者，则 $A\bigcap B\subseteq C,A\bigcup B\subseteq C$，若为后者，则 $A\bigcap B\supseteq C,A\bigcup B\supseteq C$．因此，在操作之后，其余成包含关系的集合对的数量不会减少，因此每次操作后，这个数量至少增加1．由于此数量最少为0，最多为 $C_{n}^{2}=\frac{n(n-1)}{2}$，故操作至多进行 $\frac{n(n-1)}{2}$ 次．
另一方面，我们给出操作次数达到 $\frac{n(n-1)}{2}$ 的例子．
定义集合 ${{A}_{i}}=\{i,i+1,...,i+n-2\}$，$i=1,2,...,n$，我们证明由 ${{A}_{1}},{{A}_{2}},...,{{A}_{n}}$ 出发，可以进行 $\frac{n(n-1)}{2}$ 次操作．
使用数学归纳法，当 $n=2$ 时，${{A}_{1}}=\{1\},{{A}_{2}}=\{2\}$，可进行 $\frac{2\times (2-1)}{2}=1$ 次操作．
若结论对 $n$ 成立，考虑 $n+1$ 的情况．先将 ${{A}_{1}}=\{1,2,...,n\}$ 与 ${{A}_{2}}=\{2,3,...,n+1\}$ 进行一次操作，得到的交集 $\{2,3,...,n\}$ 留下，并集继续与 ${{A}_{3}}=\{3,4,...,n+2\}$ 进行操作，得到的交集 $\{3,4,...,n+1\}$ 留下，并集继续与 ${{A}_{4}}$ 进行操作，依此类推．进行完 $n$ 次操作后，得到原来所有集合的并集 $\{1,2,...,2n\}$ 及另外 $n$ 个集合 $\{2,3,...,n\}$，$\{3,4,...,n+1\}$，……，$\{n+1,n+2,...,2n-1\}$．下面仅考虑后 $n$ 个集合之间的操作．由于将所有元素都减1并不
改变集合间的关系，故可考虑集合 $\{1,2,...,n-1\}$，$\{2,3,...,n\}$，……，$\{n,n+1,...,2n-2\}$．而由归纳假设，这些集合之间可以操作 $C_{n}^{2}=\frac{n(n-1)}{2}$ 次，故原来的 $n+1$ 个集合可以操作 $\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}=C_{n+1}^{2}$ 次，即此结论对 $n+1$ 也成立．
综上所述，操作次数的最大可能值为 $C_{n}^{2}=\frac{n(n-1)}{2}$．
当黑板上写着 $n$ 个集合时，考虑成包含关系的集合对的数量，我们证明，每次操作后，这个数量至少增加1．假设我们将 $A,B$ 变成 $A\bigcap B$ 和 $A\bigcup B$．首先 $A,B$ 不是包含关系，而 $A\bigcap B$ 和 $A\bigcup B$ 是包含关系，故这里至少增加了一对成包含关系的集合对．对于另一集合 $C$，若 $C$ 与 $A,B$ 之一成包含关系，由对称性不妨设 $A\subseteq C$，则 $A\bigcap B\subseteq C$，即 $C$ 至少与 $A\bigcap B$ 和 $A\bigcup B$ 之一成包含关系；若 $C$ 与 $A,B$ 均成包含关系，则由 $A,B$ 不成包含关系知或者 $A\subseteq C,B\subseteq C$，或者 $A\supseteq C,B\supseteq C$，若为前者，则 $A\bigcap B\subseteq C,A\bigcup B\subseteq C$，若为后者，则 $A\bigcap B\supseteq C,A\bigcup B\supseteq C$．因此，在操作之后，其余成包含关系的集合对的数量不会减少，因此每次操作后，这个数量至少增加1．由于此数量最少为0，最多为 $C_{n}^{2}=\frac{n(n-1)}{2}$，故操作至多进行 $\frac{n(n-1)}{2}$ 次．
另一方面，我们给出操作次数达到 $\frac{n(n-1)}{2}$ 的例子．
定义集合 ${{A}_{i}}=\{i,i+1,...,i+n-2\}$，$i=1,2,...,n$，我们证明由 ${{A}_{1}},{{A}_{2}},...,{{A}_{n}}$ 出发，可以进行 $\frac{n(n-1)}{2}$ 次操作．
使用数学归纳法，当 $n=2$ 时，${{A}_{1}}=\{1\},{{A}_{2}}=\{2\}$，可进行 $\frac{2\times (2-1)}{2}=1$ 次操作．
若结论对 $n$ 成立，考虑 $n+1$ 的情况．先将 ${{A}_{1}}=\{1,2,...,n\}$ 与 ${{A}_{2}}=\{2,3,...,n+1\}$ 进行一次操作，得到的交集 $\{2,3,...,n\}$ 留下，并集继续与 ${{A}_{3}}=\{3,4,...,n+2\}$ 进行操作，得到的交集 $\{3,4,...,n+1\}$ 留下，并集继续与 ${{A}_{4}}$ 进行操作，依此类推．进行完 $n$ 次操作后，得到原来所有集合的并集 $\{1,2,...,2n\}$ 及另外 $n$ 个集合 $\{2,3,...,n\}$，$\{3,4,...,n+1\}$，……，$\{n+1,n+2,...,2n-1\}$．下面仅考虑后 $n$ 个集合之间的操作．由于将所有元素都减1并不
改变集合间的关系，故可考虑集合 $\{1,2,...,n-1\}$，$\{2,3,...,n\}$，……，$\{n,n+1,...,2n-2\}$．而由归纳假设，这些集合之间可以操作 $C_{n}^{2}=\frac{n(n-1)}{2}$ 次，故原来的 $n+1$ 个集合可以操作 $\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}=C_{n+1}^{2}$ 次，即此结论对 $n+1$ 也成立．
综上所述，操作次数的最大可能值为 $C_{n}^{2}=\frac{n(n-1)}{2}$．
答案
解析
备注
