趣味の数学とプログラム。楽しい数学の世界へようこそ!

パーティー問題

パーティー問題
「パーティーで6人集めると、互いに知り合いである3人組か、互いに知らない3人組のどちらかが必ず存在する」
ラムゼー問題と呼ばれます。

グラフを用います。(グラフ理論でいうグラフは、点の集合と辺の集合で表されます。例:路線図、電気図など)

6人を点(A、B、C、D、E、F)で表し、2点間を結んだ線が2人の関係性、3点を結ぶ三角形が3人の関係性を示します。例として、Aと他の5人の関係を考えてみましょう。

互いに知り合いなら赤、知らない同士なら青に塗り分けます。線は5本なので、赤か青のどちらかが多いことになります。赤が多いとして

AとB、AとC、AとDが、それぞれ知り合いだとします。(直線AB、直線AC、直線ADを赤に)

次に、B、C、Dについて考えます。

BとCが知り合いなら直線BCは赤なので、赤い三角形ACBができます。即ち、A、B、Cが互いに知り合い同士の3人組です。

BとDが知り合いなら直線BDは赤なので、赤い三角形ADBができます。即ち、A、B、Dが互いに知り合い同士の3人組です。

CとDが知り合いなら直線DCは赤なので、赤い三角形ADCができます。即ち、A、C、Dが互いに知り合い同士の3人組です。

上のどれにも当てはまらない場合は、直線BC、直線BD、直線DCは青になり、

青い三角形BDCができます。即ち、B、C、Dが互いに知らない3人組です。

赤い三角形または青い三角形が必ず存在することがわかり、パーティー問題の証明ができました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です