在一次数学竞赛活动中，有一些参赛选手是朋友．朋友关系是相互的，如果一群参赛选手中的任何两人都是朋友，我们就称这一群选手为一个“团”（特别地，人数少于2的一群也是一个团）．
已知在这次竞赛中，最大的团（人数最多的团）的人数是一个偶数，证明：我们总能把参赛选手分配到两个教室，使得一个教室的最大团的人数等于另一个教室中的最大团的人数．（俄罗斯）
已知在这次竞赛中，最大的团（人数最多的团）的人数是一个偶数，证明：我们总能把参赛选手分配到两个教室，使得一个教室的最大团的人数等于另一个教室中的最大团的人数．（俄罗斯）
【难度】
【出处】
2007年第48届IMO试题
【标注】
【答案】
略
【解析】
我们给出分配选手的一种算法．记这两间教室分别为 $A$ 和 $B$．我们从某一个初始排列开始，靠每次调整一人从一个教室到另一个教室作若干次修改来达到目标．在这种算法的任何一步，$A$ 和 $B$ 分别表示教室 $A$ 和 $B$ 中的选手的集合，$C(A)$ 和 $C(B)$ 分别表示教室 $A$ 和教室 $B$ 中最大团的人数．
第一步：设 $M$ 是所有参赛选手中的最大团，$|M|=2m$．
将 $M$ 中的所有成员分配到教室 $A$ 中，然后把另外的所有成员分配到教室 $B$ 中．
因为 $M$ 是所有参赛选手中的最大团，我们有 $C(A)=|M|\geqslant C(B)$．
第二步：只要 $C(A)>C(B)$，我们就从教室 $A$ 中派一人到教室 $B$ 中．
注意到 $C(A)>C(B)$，这说明 $A$ 非空．
在操作每一步，$C(A)$ 减少 $1$ 而 $C(B)$ 至多增加 $1$，这样在这种操作结束时，一定有 $C(A)\leqslant C(B)\leqslant C(A)+1$．
在这种操作结束时，也一定有 $C(A)=|A|\geqslant m$，否则 $M$ 中的至少 $(m+1)$ 个选手在教室 $B$ 中，$M$ 中的至多 $(m-1)$ 个选手在教室 $A$ 中，因此 $C(B)-C(A)\geqslant (m+1)-(m-1)=2$，不可能．
第三步：设 $K=C(A)$，如果 $C(B)=K$，则结论已成立．否则我们有 $C(B)=K+1$，从上面估计知 $K=|A|=|A\bigcap M|\geqslant m,|B\bigcap M|\leqslant m$．
第四步：如果存在一个选手 $x\in B\bigcap M$ 和一个团 $C\subset B$ 使得 $|C|=k+1$ 但 $x\not\in C$，则移动 $x$ 到教室 $A$，则结论已成立．事实上，移动 $x$ 到教室 $A$ 后，教室 $A$ 中有 $M$ 的 $k+1$ 个成员，因此 $C(A)=K+1$，但 $x\not\in C,C(B)=|C|$ 是不减的，因此 $C(A)=C(B)=K+1$．
如果不存在这样的选手 $x$，则教室 $B$ 中的所有 $K+1$ 个元团都包含 $B\bigcap M$ 作为子集，这时我们进行第五步．
第五步：如果 $C(B)=K+1$，选择 $B$ 中的一个团 $C$ 使得 $|C|=K+1$，并移动 $C\setminus M$ 中的一个元到教室 $A$．
注意到 $|C|=K+1>m\geqslant |B\bigcap M|$，所以 $C\setminus M$ 是非空的．
我们每次仅移动一个人从教室 $B$ 到教室 $A$，所以 $C(B)$ 至多减少 $1$，因此在这一个步骤结束时，总有 $C(B)=K$，这时在教室 $A$ 中有个团 $A\bigcap M$，其大小 $|A\bigcap M|=K$，因此 $C(A)\geqslant K$．
下面我们证明没有比这更大的团．
设 $Q\subset A$ 是任意一个团，我们只能证明 $|Q|\leqslant K$．
事实上，教室 $A$ 中的元素 $Q$ 中，存在两种类型的选手：
（1）$M$ 中的一些成员，因为 $M$ 是一个团，他们与 $B\bigcap M$ 中的所有成员都是朋友；
（2）在第五步从教室 $B$ 到教室 $A$ 中的选手，这种团中的每一个都在团 $B\bigcap M$，因此他们也与 $B\bigcap M$ 的所有成员都是朋友．
因此，$Q$ 的所有成都与 $B\bigcap M$ 的所有成员是朋友，集合 $Q$ 和 $B\bigcap M$ 本身也是团，所以 $Q\bigcup (B\bigcap M)$ 也是团．又因为 $M$ 是最大的团，所以
$|M|\geqslant |Q\bigcup (B\bigcap M)|=|Q|+|B\bigcap M|=|Q|+|M|-|A\bigcap M|$
因此 $|Q|\leqslant |A\bigcap M|=K$．
故在第五步后，我们有 $C(A)=C(B)=K$．
第一步：设 $M$ 是所有参赛选手中的最大团，$|M|=2m$．
将 $M$ 中的所有成员分配到教室 $A$ 中，然后把另外的所有成员分配到教室 $B$ 中．
因为 $M$ 是所有参赛选手中的最大团，我们有 $C(A)=|M|\geqslant C(B)$．
第二步：只要 $C(A)>C(B)$，我们就从教室 $A$ 中派一人到教室 $B$ 中．
注意到 $C(A)>C(B)$，这说明 $A$ 非空．
在操作每一步，$C(A)$ 减少 $1$ 而 $C(B)$ 至多增加 $1$，这样在这种操作结束时，一定有 $C(A)\leqslant C(B)\leqslant C(A)+1$．
在这种操作结束时，也一定有 $C(A)=|A|\geqslant m$，否则 $M$ 中的至少 $(m+1)$ 个选手在教室 $B$ 中，$M$ 中的至多 $(m-1)$ 个选手在教室 $A$ 中，因此 $C(B)-C(A)\geqslant (m+1)-(m-1)=2$，不可能．
第三步：设 $K=C(A)$，如果 $C(B)=K$，则结论已成立．否则我们有 $C(B)=K+1$，从上面估计知 $K=|A|=|A\bigcap M|\geqslant m,|B\bigcap M|\leqslant m$．
第四步：如果存在一个选手 $x\in B\bigcap M$ 和一个团 $C\subset B$ 使得 $|C|=k+1$ 但 $x\not\in C$，则移动 $x$ 到教室 $A$，则结论已成立．事实上，移动 $x$ 到教室 $A$ 后，教室 $A$ 中有 $M$ 的 $k+1$ 个成员，因此 $C(A)=K+1$，但 $x\not\in C,C(B)=|C|$ 是不减的，因此 $C(A)=C(B)=K+1$．
如果不存在这样的选手 $x$，则教室 $B$ 中的所有 $K+1$ 个元团都包含 $B\bigcap M$ 作为子集，这时我们进行第五步．
第五步：如果 $C(B)=K+1$，选择 $B$ 中的一个团 $C$ 使得 $|C|=K+1$，并移动 $C\setminus M$ 中的一个元到教室 $A$．
注意到 $|C|=K+1>m\geqslant |B\bigcap M|$，所以 $C\setminus M$ 是非空的．
我们每次仅移动一个人从教室 $B$ 到教室 $A$，所以 $C(B)$ 至多减少 $1$，因此在这一个步骤结束时，总有 $C(B)=K$，这时在教室 $A$ 中有个团 $A\bigcap M$，其大小 $|A\bigcap M|=K$，因此 $C(A)\geqslant K$．
下面我们证明没有比这更大的团．
设 $Q\subset A$ 是任意一个团，我们只能证明 $|Q|\leqslant K$．
事实上，教室 $A$ 中的元素 $Q$ 中，存在两种类型的选手：
（1）$M$ 中的一些成员，因为 $M$ 是一个团，他们与 $B\bigcap M$ 中的所有成员都是朋友；
（2）在第五步从教室 $B$ 到教室 $A$ 中的选手，这种团中的每一个都在团 $B\bigcap M$，因此他们也与 $B\bigcap M$ 的所有成员都是朋友．
因此，$Q$ 的所有成都与 $B\bigcap M$ 的所有成员是朋友，集合 $Q$ 和 $B\bigcap M$ 本身也是团，所以 $Q\bigcup (B\bigcap M)$ 也是团．又因为 $M$ 是最大的团，所以
$|M|\geqslant |Q\bigcup (B\bigcap M)|=|Q|+|B\bigcap M|=|Q|+|M|-|A\bigcap M|$
因此 $|Q|\leqslant |A\bigcap M|=K$．
故在第五步后，我们有 $C(A)=C(B)=K$．
答案
解析
备注
