ラムゼーの定理と６人の問題

更新日時 2021/03/07

ラムゼー問題

6人いると「互いに知り合いである3人組」か「互いに知らない3人組」が存在することを証明せよ。

「パーティー問題」「Theorem on friends and strangers」などとも呼びます。

数学オリンピックではこのような問題を解けることが大事になります。数オリに出ない人も非常に有名な問題なので知っておくとよいでしょう。

問題の解答

方針

言葉で表現すると大変なのでグラフを用います。つまり，6人をそれぞれ点で表し，知り合いを赤い線で結び，知らない人を青い線で結びます。このグラフにおいて赤い三角形か青い三角形が存在することを示せばよいのです。

証明

ラムゼー問題の解答

1つの点 $A$ に注目すると，5本枝が出ているので，そのうち3本以上は同じ色である。赤が3本以上出ているとして一般性を失わない。その相手を $B, C, D$ とする。

となり，いずれの場合も赤い三角形または青い三角形が存在することが分かる。

このようにグラフを用いると簡潔に表現できます。数学オリンピックでも「記述の道具」としてグラフ理論を知っていると便利です。→グラフ理論の基礎

ラムゼー数は6

ちなみに，5人の場合は図のように頑張れば赤い三角形も青い三角形もつくらずにグラフがかけます。

つまり，どの3人に注目しても知り合いである2人も知り合いでない2人も存在するのです。

上記の問題を一般化します。「完全グラフ」とは全ての頂点間に枝が張り巡らされたグラフのことです。

ラムゼーの定理

$A,B$ は任意の定数とする。頂点数 $n$ の完全グラフの枝を赤と青に塗り分けるとき， $n$ が十分大きければ「頂点数 $A$ の赤い完全グラフ」または「頂点数 $B$ の青い完全グラフ」が必ず存在する。この条件を満たす最小の $n$ をラムゼー数と呼び， $R(A,B)$ と表す。

ラムゼー数が無限大に吹っ飛ばずにきちんと存在するというのがラムゼーの定理です。

定理の主張はほとんど自明に思えるかもしれませんが，厳密に示そうとするとけっこう大変なようです。

さきほど示したことはラムゼー数 $R(3,3)=6$ ということになります。
（パーティー問題の結果が $R(3,3)\leq 6$ を表しており，頂点数 $5$ の場合にうまく塗り分けできることが $R(3,3) > 5$ を表しています。）
$A,B$ が一般の場合にラムゼー数を求めるのは非常に難しい問題です。
塗り分けの色の数を増やしてさらに一般化することもできます。
IMO 1964第4問は，六人の問題とその証明を知っていると非常に有利になる問題でした。練習問題にどうぞ！

問題

17人それぞれが他の全員と互いに手紙をやりとりしている．その手紙では三つの話題のみがやりとりされている．そして，同じ二人組の間でなされる話題は常に同じ（一つの）話題である．

このとき，互いに同じ話題の手紙をやりとりした三人組が存在することを証明せよ．

6人の問題の証明はなかなか美しいので個人的に推しています。