鳩の巣原理

靴下の引き出しに、黒い靴下と白い靴下だけが混ざっていると想像してみてください。明かりを消した暗闇で、少なくとも何枚取り出せば、必ず同じ色のペアができるでしょうか。答えは3枚です。色という「入れ物」は2つしかないのに靴下を3枚取ったのですから、少なくとも1色は2枚重なるしかないからです。

これが鳩の巣原理の基本の姿です。鳩が10羽、巣が9つあるなら、どれだけ均等に分けて入れようとしても、どれか1つの巣には必ず2羽以上が入ることになります。9羽が1つずつ巣を占めたら、残る1羽は、すでに誰かが入っている巣に加わるしかないからです。

あまりに当たり前で、拍子抜けしてしまうかもしれません。けれども、この当たり前さが、数学ではとても強力な証明の道具になります。すべての場合を一つひとつ確かめなくても、ある状況が「必ず起こる」ことをはっきり示せるからです。

人口900万人を超えるソウル(韓国の首都)に、髪の毛の本数がまったく同じ人はいるでしょうか。市民全員の髪を1本ずつ数えなくても、鳩の巣原理を使えば1秒で「必ずいる」と答えられます。

人の髪の毛は、多くてもふつう15万本ほどです。ここでは余裕をもって、最大50万本としてみましょう。すると、髪の毛の本数でつくれる「巣」は、0本から50万本まで、全部で50万1個になります。

ところが、ソウル市民という「鳩」は900万人を超えます。50万個の巣に900万羽の鳩を入れるようなものです。したがって、ソウルには髪の毛の本数がぴったり一致する人たちのグループが、必ず存在します。鳩の巣原理は、巨大な都市に隠れたルールを一瞬で明らかにしたのです。

鳩の巣原理は、19世紀の数学者ディリクレが体系的にまとめたため、「ディリクレの引き出し原理」とも呼ばれます。この原理は、単に「2つ以上重なる」で終わらず、もっと広く拡張できます。

たとえば、21羽の鳩を10個の巣に入れるとどうなるでしょうか。できるだけ均等に2羽ずつ入れても、1羽が余ります。そのため、このときは少なくとも1つの巣に3羽以上が入ることになります。これを「一般化された鳩の巣原理」といいます。

コンピューターサイエンスでも、この原理は重要な役割を果たします。どんなにすぐれた圧縮技術でも、「すべてのファイルのサイズを必ず小さくする魔法の圧縮ソフト」は決してつくれない、と証明するときに使われます。巣より鳩が多い状況は、数学やアルゴリズムのあちこちで、大切な限界を教えてくれるのです。