MathLabs

第3問

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