鳩の巣原理（はとのすげんり、）またはディリクレの箱入れ原理（ディリクレのはこいれげんり、）、あるいは部屋割り論法とは、"n" 個の物を "m" 個の箱に入れるとき、"n" > "m" であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、"m" 個の箱には最大 "m" 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。この原理に関する最初の記述は、ディリクレが1834年に "Schubfachprinzip"（「引き出し原理」）の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある（同名の、調和関数における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。わかりやすい例をあげよう。野球をやりたい子どもが5人いるが、チームは4つしかなかったとする。ここで、5人の全員が、自分以外の4人の誰とも同じチームでプレーするのを拒否すると、問題が起こる。鳩の巣原理によれば、5人を4つのチームに割り当てようとすると、必ず誰か2人は同じチームになってしまう。お互い同じチームでプレーするのは嫌がっているのだから、結局、野球ができる最大の人数は4人になってしまう。こうしてみると、鳩の巣原理は一見自明に思われるかもしれないが、突拍子もない結果を論証するのに使われることもある。たとえば「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」。証明してみよう。ふつう、髪の毛の本数は15万本ほどであるから、100万本以上の髪の毛を持っている人間はいないと考えることができる。ロンドンの人口は100万を超える。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てるなら、（当然の下限である0本から上限として置いた99万9999本までの巣に100万を超える人々を割り当てるのだから）少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。もう1つのきわめて有名な例は、世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる、というものである。詳細は、ラムゼーの定理および組合せ数学のラムゼー理論の項を参照。鳩の巣原理は、計算機科学の分野ではしばしば現れる。たとえば、ハッシュテーブルでは、通常利用されるキーの種類は配列のインデックスの取りうる値の数を上回ることから、ハッシュ値の衝突は避けられない。この衝突を回避できるハッシュアルゴリズムが存在しえないことは、この原理によって証明されている。また、どんな可逆圧縮アルゴリズムも特定のデータに対しては、元よりもデータ量の大きな形に変換せざるを得ない。「圧縮」アルゴリズムである以上、あるnバイトの元データを(n-1)バイト以下に変換できるはずであるが、このとき、元々(n-1)バイト以下である 2-1 種類の元データのうち少なくとも1つをnバイト以上に変換するようにしなければ、2 種類の元データを 2-1 通りのデータに変換することになる。鳩の巣原理により、少なくとも1つの変換後データは2つ以上の元データに対応することになり、伸張はどうなるのか不明になってしまう。前述した「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」ということの証明の面白いところは、同じ本数の髪の毛の人が存在することを証明しているにもかかわらず、具体的にどの2人が同じ本数の髪の毛を持つのかは分からないということである。鳩の巣原理を使った証明にはこのような特徴をもつものが多く、何らかの性質を満たすものが存在することを証明するにもかかわらず、どれがその性質を満たすのかについては何も分からない。もちろん100万人以上いるロンドン市民の髪の毛の本数を全員チェックすればどの２人が同じ本数の髪の毛を持つのか分かるが、このような非効率的なことをしなくても定理が証明できるのが鳩の巣原理の利点である。(チェックが多項式時間でできないにもかかわらず、鳩の巣原理により存在性のみが言えるもある )。この特徴のため、鳩の巣原理は定理を証明する強力な道具になる。実際、無限がからんだ場合、鳩の巣原理を使わないとおよそ証明できない命題を証明できる場合がある。前述の例を少しだけ改変して、「30万以上の人口を持つ任意の都市Xに対し、Xには同じ本数の髪の毛を持った少なくとも2人の人間が存在する」という命題を考える。世界にあるそのような都市の数が有限であれば、全ての都市にいる全ての人間の髪の毛の本数を数えることで上述の命題の真偽がチェックできるが、そのような都市の数が無限であれば、全ての都市についてチェックするのは原理的に不可能である。しかし鳩の巣原理を使えば、たとえそのような都市の数が無限であってもこの定理が真であることを一瞬にして証明できる。鳩の巣原理を一般化する。"n" 個の離散的な対象を "m" 個の入れ物に割り当てるとすると、少なくとも1個の入れ物には、formula_1 個より少なくない対象が割り当てられている。ここで formula_2 は天井関数のことであり、"x" に等しいか、"x"より大きい最小の整数を表す。鳩の巣原理はさらに一般化され、グラフなどのより複雑な数学的構造、また算術的な関係などに対しても類似の定理が知られている（ラムゼーの定理など）。それらをラムゼー型の定理という。濃度に関する一般化を述べる為にまず鳩の巣原理を集合の言葉で言い換える。"A" を鳩の集合とし、"B" を巣の集合とする。すると、鳩に巣を対応させる行為は "A" の元に "B" の元を対応させる写像"f" とみなせる。鳩の巣原理は、"A" 、"B" が有限集合で、 "A" の元の数が "B" の元の数より大きいとき、2羽の鳩が同じ巣に入ることを意味しており、これはすなわち、"f" が単射でない事と同値である。より一般に（有限とは限らない）集合"A"、"B"について、"f"を"A"から"B"への関数とする。このとき"A"の濃度が"B"の濃度より大きければ、"f"は単射ではありえない（このことは濃度の大小の定義から直ちに出る）。次に、確率的な一般化を述べる。"n" 羽の鳩が "m" 個のそれぞれの巣へ 1 / "m" の確率で入れられるとすると、少なくとも1つの巣が2羽以上の鳩に占められる確率は、ただし、"m" は下降階乗冪。"n" = 0, 1（で "m" > 0）のとき、確率は0である。言い換えれば、鳩が1羽のとき、衝突は起こらない。"n" > "m" であれば（鳩が巣より多ければ）、通常の鳩の巣原理を使い、確率は1である。しかし、たとえ鳩が巣より少なかったとしても（"n" < "m" でも）、巣への鳩の割当ての無作為性により、衝突が起こる可能性は十分にある。たとえば4個の巣に2羽の鳩ならば、少なくとも1つの巣が2羽以上の鳩に占められる確率は 25%。10個に5羽なら確率は 69.76% であり、20個に10羽なら 93.45% である。この問題は、もっと十分な長さでは、誕生日のパラドックスで扱われている。

出典:wikipedia