鳩の巣原理
鳩の巣原理（はとのすげんり、英: Pigeonhole principle）[1]、またはディリクレの箱入れ原理（ディリクレのはこいれげんり、英: Dirichlet's box principle, Dirichlet's drawer principle）、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。
鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。
この原理に関する最初の記述は、ペーター・グスタフ・ディリクレが1834年に "Schubfachprinzip"（「引き出し原理」）の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある（同名の、調和関数における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。鳩の巣原理という訳語は pigeonhole が持つ「鳩小屋の仕切り巣箱」という意味に着目したものであるが、pigeonhole の第一義は仕切り箱や分類棚であるからこれは誤訳なのだと上野健爾は指摘している[2]。19世紀から整数論で使われてきた歴史を踏まえ上野はこの原理をディリクレの部屋割り論法と呼んでいる。
この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。
例
3つの巣があり、4羽の鳩が巣に戻るとする。1羽目から3羽目まではそれぞれ鳩のいない巣に戻ることができるが、4羽目はすでに鳩のいる巣しか選べず、その巣には2羽の鳩がいることとなる。このように、どこかの巣には必ず鳩が2羽以上いる[3]。
計算機科学における鳩の巣原理
鳩の巣原理は計算機科学の分野でも証明に使われる。
ハッシュテーブルにおいて想定されるキーの種類がテーブルの配列長を上回る場合、テーブルのインデックスが衝突しえないような値を出力するハッシュ関数（完全ハッシュ関数）は存在しないということが、この原理によって証明できる。
可逆圧縮アルゴリズムの圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在することが、鳩の巣原理を用いて証明できる。具体的には下記の通り[4][5]。
- 「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
- 圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする（MとNの単位はビット）。
- 圧縮処理後にデータサイズが小さくなるため、N < Mである。さらに圧縮処理後にデータサイズが大きくなる入力データが存在しないため、Nビットのデータは圧縮処理後もNビットとなる。
- Nビットのデータは2N種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2N+1種類存在する。
- しかしNビットのデータが2N種類しかないので、鳩の巣原理により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能（どちらに戻すべきか判別できない）である。
- したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」（可逆圧縮アルゴリズムではない）か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。
鳩の巣原理の一般化
鳩の巣原理を一般化する。n 個の離散的な対象を m 個の入れ物に割り当てるとすると、少なくとも1個の入れ物には、
鳩の巣原理と同じ種類の言葉
- 鳩の巣原理のページへのリンク
