鳩の巣原理
鳩の巣原理（はとのすげんり、英: 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個の入れ物には、 個より少なくない対象が割り当てられている。ここで は天井関数のことであり、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) は下降階乗冪。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% である。この問題は、もっと十分な長さでは、誕生日のパラドックスで扱われている。
脚注
[編集]- ^ “Pigeonhole principle”. www.britannica.com. Britannica. 2020年9月28日閲覧。
- ^ 上野健爾『ジーゲル: 人と数学』現代数学社〈双書・大数学者の数学〉、2022年、57頁。
- ^ 芳沢光雄 (12 November 2021). "当たり前のようで奥が深い 「鳩の巣原理」を知ろう". 朝日新聞EduA. 2023年9月5日閲覧。
- ^ Bell, Tim (28 September 2015). "Surprising Computer Science". In Brodnik, Andrej; Vahrenhold, Jan (eds.). Informatics in Schools. Curricula, Competences, and Competitions. 8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives (英語). Vol. 9378. Springer. pp. 8–9. doi:10.1007/978-3-319-25396-1. ISBN 978-3-319-25396-1. S2CID 26313283。
- ^ Sayood, Khalid, ed. (18 December 2002). Lossless Compression Handbook (Communications, Networking and Multimedia) (英語) (1st ed.). Academic Press. p. 41. ISBN 978-0-12390754-7。