MathLabs

第3题

在一场数学竞赛中，有些参赛者彼此是朋友。朋友关系总是相互的。若一个参赛者群体中的任意两人都是朋友，则称该群体为团。（特别地，少于两名参赛者的任意群体都是团。）团中成员的数目称为其大小。已知在这场竞赛中，团的最大大小为偶数，证明可以把参赛者安排到两个房间，使一个房间内所含团的最大大小等于另一个房间内所含团的最大大小。
第 3/4 步：当 B 的每个 (k+1)-团都包含 B cap M 时，从每个团剥离一名非 M 成员
上一步下一步
通俗地说

由于 ∣C∣=k+1>m≥∣B∩M∣|C| = k+1 > m \ge |B \cap M|，BB 的每个 (k+1)(k+1)-团都必须含有 MM 外的成员；把这样的人移到 AA 会破坏 CC，而每个被移动者都与 B∩MB \cap M 的所有成员是朋友。

forall,CsubseteqBtextwith∣C∣=k+1:BcapMsubseteqCimpliesCsetminusMneemptyset\\forall\\, C \\subseteq B \\text{ with } |C|=k+1:\\ B \\cap M \\subseteq C \\implies C \\setminus M \\ne \\emptyset
详细分析

若第2步不适用，则每个大小为 k+1k+1 的团 C⊆BC \subseteq B 都包含 B∩MB \cap M。由于 ∣C∣=k+1>m≥∣B∩M∣|C| = k+1 > m \ge |B \cap M|，C∖MC \setminus M 非空。当 c(B)=k+1c(B) = k+1 时，选择这样的 CC，把 C∖MC \setminus M 中一名成员从 BB 移到 AA；每次移动使 c(B)c(B) 至多减少 11，并保持 B∩MB \cap M 不变，所以在 c(B)=kc(B) = k 时停止。每个被移动者都属于包含 B∩MB \cap M 的团，因此与 B∩MB \cap M 的所有成员是朋友。