第3問

数学コンテストに参加する競技者の中には友人同士の者がいる。友情は常に相互的である。任意の二人が友人であるような競技者の集合をクリークと呼ぶ。（特に、2人未満の任意の集合もクリークである。）クリークの要素数をそのサイズと呼ぶ。このコンテストでクリークの最大サイズが偶数であるとき、競技者を二つの部屋に配置して、一方の部屋に含まれるクリークの最大サイズと他方の部屋に含まれるクリークの最大サイズが等しくなるようにできることを証明せよ。

ステップ 4/4: ステップ3の移動後も c(A) が k に等しいことを示す

前のステップ次のステップ

ざっくり言うと

$A$ の全員（ $A \cap M$ とステップ3で移った人々）は $B \cap M$ の全員と友人なので、任意のクリーク $Q \subseteq A$ は $B \cap M$ と合わせて全体の最大値 $|M|$ を超えないクリークになる。

Q \\subseteq A \\text{ clique} \\implies Q \\cup (B \\cap M) \\text{ is a clique} \\implies |Q| + |B \\cap M| \\le |M| \\implies |Q| \\le |A \\cap M| = k

詳しい解説

最後の部屋 $A$ では $A \cap M$ がサイズ $k$ のクリークなので $c(A) \ge k$ 。任意のクリーク $Q \subseteq A$ の各人は $A \cap M$ に属するかステップ3で移された人であり、いずれも $B \cap M$ の全員と友人である。よって $Q \cup (B \cap M)$ はクリークとなる。 $M$ の最大性から $|M| \ge |Q \cup (B \cap M)| = |Q| + |B \cap M| = |Q| + |M| - |A \cap M|$ 、従って $|Q| \le |A \cap M| = k$ 。ゆえに $c(A) = k = c(B)$ である。