6人以上の人が集まると、互いに知り合いの3人か、見ず知らずの3人がいる。

先日、読むだけで論理力が自然と鍛えられる本『ピジョンの誘惑』を紹介しました。収録されているすべての問題が「鳩の巣原理」というたった一つの法則にこだわった（その法則さえ知っていれば解ける）パズルです。標題の問題は、『ピジョンの誘惑』を紹介したエントリーで「最も感動した問題」として挙げたものの一つです。今回は、その解説を試みます。

まず「鳩の巣原理」から

「鳩が10羽いるのに、巣が9個しかないならば、どこかの巣には 2羽の鳩が入ることになる。」これを「鳩の巣原理」と言います。

もちろん、鳩10羽と巣9個の数は本質的ではありません。一般的に言えば、「巣の数より鳩の数の方が多ければ、どこかの巣には 2羽以上の鳩が入ることになる」ということです。

この原理は証明しなくても明らかでしょう。

問題中の用語の意味を確認

言葉の意味が明確でないといけませんから、標題の問題にある用語について、念のため確認しておきます。

「6人以上の人が集まると」ということは、人数は6人でも、1万人でも、10億人でもよくて、6人以上であれば人数を問わないということです。

「知り合い」ということは、相手のことをお互いに知っている関係のことを言います。逆に、「見ず知らず」とは「知り合いではない」ということ、つまり少なくとも一方が相手のことを知らない関係のことを言います。私は安倍総理を知っていますが、安倍総理は私のことを知らないので、一方だけが知っていても「見ず知らず」の関係とします。

ですから、ある2人の関係は必ず、「知り合い」か「見ず知らず（知り合いではない）」のどちらかとなります。

6人の場合を示せば十分

実はこの問題、6人の場合で成立することを証明しておけば十分です。どんな6人の場合でも成り立つことを証明しておけば、1億人の場合であっても、そのうちのどの6人を選んでも成り立つわけですから、一般的にN人の場合（N≧6）を証明する必要はありません。
つまり標題は、「6人が集まると、互いに知り合いの3人か、見ず知らずの3人がいる」が証明できれば十分です。

ここで問題の意味合いを冷静に考えてみる

グローバルに考えて、地球上の約70億人の人間から適当に6人を選ぶと、「見ず知らず」の3人は必ずいそうですから、ほぼいつでも成り立ちそうです。逆にローカルに考えて、同じ学年の同級生から6人を選ぶと、「互いに知り合い」の3人は必ずいそうですから、この場合もほぼいつでも成り立ちそうです。

今あげた両極端の場合はほぼ確実に起こりそうだと分かりますが、ほどほどに知り合いがいそうな状況、例えば100軒ぐらいからなる町内会から6人を選んだ場合はどうでしょうか？　この命題のすごいところは、こんな場合でも常に、互いに知り合いの3人か見ず知らずの3人がいるという事実です。

つまり、互いに知り合いの3人もおらず、見ず知らずの3人もいないという中途半端な状態はありえない、ということです。

5人の場合はどうか

「6人以上の場合」で成り立つ命題ですから、5人の場合はどうか考えてみました。
ちょっと時間がかかりましたが、下図のような関係のときに「互いに知り合いの3人」も「見ず知らずの3人」もいないことが分かりました。

f:id:igawajp:20150426165319j:plain

線が結ばれているのが「互いに知り合いの関係」（例えばAとB）で、結ばれていないのが「見ず知らずの関係」（例えばAとC）です。この五角形の関係だと、「互いに知り合いの3人」も「見ず知らずの3人」もいないことが分かります。

ここでようやく証明の本丸へ

ここから本題に入ります。6人の人が集まっているとして、そのうちの一人をAさんとします。
まず、残りの5人をAさんの知り合いと、知り合いではない人の2グループに分けて考えます。「鳩の巣原理」により（ちょっと変則的ですが）、どちらかのグループには3人以上が含まれます。そうでなければ、どちらのグループも2人以下になるので、合わせても5人にならないからです。

ここで仮に、知り合いのグループの方に3人以上の人がいるとします。そのうちの2人が知り合い（下図左）ならば、その2人とAさんが互いに知り合いの3人になります。そうでないとすると（下図右）、そのグループの全員がお互いに知り合いではないので、見ず知らずの3人がいることになります。

f:id:igawajp:20150505114629j:plain