鳩の巣原理

鳩の巣原理（はとのすげんり、Pigeonhole principle）またはディリクレの箱入れ原理（ディリクレのはこいれげんり、Dirichlet's box principle, Dirichlet's drawer principle）、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。鳩の巣原理は数え上げ問題の例の一つで、一対一対応ができない無限集合など、多くの形式的問題に適用できる。この原理に関する最初の記述は、ディリクレが1834年に \"Schubfachprinzip\"（「引き出し原理」）の名前で書いたものであると信じられている。また、ディリクレが発見したためディリクレの原理と呼ばれることもある（同名の、調和関数における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。この原理は、ディオファントス近似において、小さな係数を持ち、なおかつ指定された解をもつ線形方程式系の存在を示すために応用される。この方法は、「ジーゲルの補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の定理を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。