鳩の巣原理
10羽のハトが9個の巣に入ると、少なくとも1つの巣には2羽以上が入ることになる、当たり前だけど強力な理屈です。
定義 鳩の巣原理（部屋割り論法）とは、入れようとする物の数が箱の数よりも多いとき、少なくとも1つの箱には2つ以上の物が必ず入るという数学の基本原理です。当たり前のように思えますが、複雑な数学やコンピュータ科学の問題を鮮やかに解き明かす強力な道具です。
10羽のハトと9個の巣
靴下の引き出しに、黒い靴下と白い靴下だけが入っているところを想像してみてください。暗闇の中で何枚取り出せば、絶対に同じ色のペアが作れるでしょうか？ 正解は3枚です。靴下の色という「箱」は2つしかないのに3枚取り出したので、少なくともどちらか1色は2枚重ならざるを得ないからです。
これこそが鳩の巣原理の基本的な姿です。ハトが10羽いて鳩の巣が9個あるとすれば、どれほどハトを均等に分けようとしても、どれか1つの巣には必ず2羽以上が入らなければなりません。ハト9羽が1個ずつ巣を占領した時点で、残りの1羽はすでに誰かが入っている巣に入るしかないからです。
あまりにも当たり前で、拍子抜けするかもしれません。しかし、この当たり前の事実が、数学ではとてつもなく強力な証明の道具になります。すべての場合をいちいち調べ上げなくても、ある状況が「絶対に起こる」ことを確実に証明してくれるからです。
東京で髪の毛の本数が完全に同じ人はいる？
人口1400万人を超える大都市・東京で、髪の毛の本数が1本違わず完全に同じ人は存在するでしょうか？ 都民全員の髪の毛を1本ずつ数えなくても、鳩の巣原理を使えば1秒で「絶対にいる」と答えられます。
人の髪の毛の本数は、多くても普通は10万〜15万本ほどです。かなり多めに見積もって、最大50万本としましょう。すると、髪の毛の本数で作れる「巣」は、0本から50万本までの合計50万1個になります。
しかし、東京都民という「ハト」は1400万人以上もいます。約50万個の巣に、1400万羽のハトを詰め込むようなものです。したがって、東京には髪の毛の本数が完全に一致する人たちの集まりが絶対に存在します。鳩の巣原理が、巨大な都市に潜む法則を一瞬で解き明かしたのです。
もう少し詳しく言うと
鳩の巣原理は、19世紀の数学者ディリクレが体系的に整理したことから「ディリクレの部屋割り論法」とも呼ばれます。この原理は、単に「2つ以上重なる」だけにとどまらず、さらに広く拡張できます。
例えば、21羽のハトを10個の巣に入れるとどうなるでしょうか？ ハトをできるだけ均等に2羽ずつ分けても1羽余ってしまいます。そのため、この場合は少なくとも1つの巣に3羽以上が入ることになります。これを「一般化された鳩の巣原理」と呼びます。
コンピュータ科学においても、この原理は極めて重要な役割を果たします。どれほど優れた圧縮技術であっても、「すべてのファイルのサイズを必ず小さくできる魔法の圧縮プログラム」は絶対に作れない、という事実を証明するときなどに使われます。巣よりもハトが多いという状況は、数学やアルゴリズムのあちこちで決定的な限界を教えてくれるのです。
🤔 よくある誤解
鳩の巣原理は、どの巣にハトが重なるかまで正確に教えてくれる。
どの巣で重なるかまでは分からず、ただ「重複する巣が少なくとも1つは必ず存在する」という事実だけを保証します。
🧺 日常で出会う場面
入れる箱の数よりも物の数が多いなら、少なくとも1つの箱には2つ以上の物が重ならざるを得ないという数学の原理です。