MathLabs

第3题

在一场数学竞赛中，有些参赛者彼此是朋友。朋友关系总是相互的。若一个参赛者群体中的任意两人都是朋友，则称该群体为团。（特别地，少于两名参赛者的任意群体都是团。）团中成员的数目称为其大小。已知在这场竞赛中，团的最大大小为偶数，证明可以把参赛者安排到两个房间，使一个房间内所含团的最大大小等于另一个房间内所含团的最大大小。
第 1/4 步：在房间 A 中放置最大团 M，并迁移成员直到 c(A) <= c(B)
上一步下一步
通俗地说

开始时把 MM 全部放入房间 AA，有 c(A)=2m≥c(B)c(A) = 2m \ge c(B)；逐一将成员从 AA 移到 BB，使每一步 c(A)c(A) 减少 11，而 c(B)c(B) 至多增加 11。因此当 c(A)>c(B)c(A) > c(B) 首次不成立时，c(B)c(B) 为 kk 或 k+1k+1，且因 MM 的偶数大小为 2m2m，有 k≥mk \ge m。

∣M∣=2m,quadtextstopwhenk=c(A)lec(B)lek+1,quadk=∣A∣=∣AcapM∣gem|M| = 2m, \\quad \\text{stop when } k = c(A) \\le c(B) \\le k+1, \\quad k = |A| = |A \\cap M| \\ge m
示意性的 K4 朋友关系图：四个顶点构成大小为偶数的最大团；该图不表示房间划分。
四个顶点的完全图，示意大小为偶数的最大团，但不表示两间房的安排。
详细分析

令 c(X)c(X) 表示房间 XX 内团的最大大小。固定大小为 ∣M∣=2m|M| = 2m 的最大团 MM，令 A=MA = M，BB 为其余参赛者，因此 c(A)=2m≥c(B)c(A) = 2m \ge c(B)。当 c(A)>c(B)c(A) > c(B) 时把一人从 AA 移到 BB；每次移动使 c(A)=∣A∣c(A) = |A| 减少 11，而 c(B)c(B) 至多增加 11。循环停止且 k=c(A)=∣A∣=∣A∩M∣k = c(A) = |A| = |A \cap M| 时，k≤c(B)≤k+1k \le c(B) \le k+1。另外 k≥mk \ge m：否则 ∣A∩M∣≤m−1|A \cap M| \le m-1 且 ∣B∩M∣≥m+1|B \cap M| \ge m+1，将有 c(B)−c(A)≥(m+1)−(m−1)=2c(B) - c(A) \ge (m+1) - (m-1) = 2，与停止时的 c(B)≤c(A)+1c(B) \le c(A)+1 矛盾。若 c(B)=kc(B) = k 则已完成；以下假设 c(B)=k+1c(B) = k+1（且 k≥m≥∣B∩M∣k \ge m \ge |B \cap M|）。