鳩の巣原理のソースを表示

[[ファイル:TooManyPigeons.jpg|thumb|right|''n'' = 10 羽の鳩が ''m'' = 9 つの巣の中にいる。したがって少なくとも1つの巣には2羽以上の鳩がいる。]]
'''鳩の巣原理'''（はとのすげんり、{{lang-en-short|''Pigeonhole principle''}}）<ref>{{Cite web |url = https://www.britannica.com/topic/pigeonhole-principle|title = Pigeonhole principle|website = www.britannica.com|publisher = Britannica|date = |accessdate = 2020-09-28}}</ref>、または'''ディリクレの箱入れ原理'''（ディリクレのはこいれげんり、{{lang-en-short|''Dirichlet's box principle'', ''Dirichlet's drawer principle''}}）、あるいは'''部屋割り論法'''とは、''n'' 個の物を ''m'' 個の箱に入れるとき、''n'' > ''m'' であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、''m'' 個の箱には最大 ''m'' 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。

鳩の巣原理は[[組合せ数学|数え上げ問題]]の例の一つで、[[全単射|一対一対応]]ができない[[無限集合]]など、多くの形式的問題に適用できる。

この原理に関する最初の記述は、[[ペーター・グスタフ・ディリクレ]]が[[1834年]]に "''Schubfachprinzip''"（「'''引き出し原理'''」）の名前で書いたものであると信じられている。また、ディリクレが発見したため'''ディリクレの原理'''と呼ばれることもある（同名の、[[調和関数]]における最小原理と混同してはいけない）。日本語では、以上の「—原理」はすべて「—論法」と訳されることもある。鳩の巣原理という訳語は pigeonhole が持つ「鳩小屋の仕切り巣箱」という意味に着目したものであるが、pigeonhole の第一義は仕切り箱や分類棚であるからこれは誤訳なのだと[[上野健爾]]は指摘している<ref>
{{cite book|和書
| author-link=上野健爾
| author=上野健爾
| title=ジーゲル: 人と数学
| series=双書・大数学者の数学
| year=2022
| publisher=現代数学社
| page = 57
}}
</ref>。19世紀から整数論で使われてきた歴史を踏まえ上野はこの原理を'''ディリクレの部屋割り論法'''と呼んでいる。

この原理は、[[ディオファントス近似]]において、小さな係数を持ち、なおかつ指定された解をもつ[[線形方程式系]]の存在を示すために応用される。この方法は、「[[カール・ジーゲル|ジーゲル]]の補題」という名前で知られる。発見者であるディリクレ自身、そのような高度な技巧を経由するものではないがディオファントス近似に関する彼の[[ディリクレのディオファントス近似定理|定理]]を証明するためにこの原理を用いている。また、さらに一般的な数学的構造においても類似の定理が数多く存在することが知られている。

== 例 ==
3つの巣があり、4羽の鳩が巣に戻るとする。1羽目から3羽目まではそれぞれ鳩のいない巣に戻ることができるが、4羽目はすでに鳩のいる巣しか選べず、その巣には2羽の鳩がいることとなる。このように、どこかの巣には必ず鳩が2羽以上いる<ref>{{Cite web2|language=ja|url=https://www.asahi.com/edua/article/14465343|author=芳沢光雄|author-link=芳沢光雄|title=当たり前のようで奥が深い 「鳩の巣原理」を知ろう|website=朝日新聞EduA|date=2021年11月12日|access-date=2023年9月5日}}</ref>。

== 計算機科学における鳩の巣原理 ==
鳩の巣原理は[[計算機科学]]の分野でも証明に使われる。

[[ハッシュテーブル]]において想定されるキーの種類がテーブルの配列長を上回る場合、テーブルのインデックスが衝突しえないような値を出力するハッシュ関数（完全ハッシュ関数）は存在しないということが、この原理によって証明できる。

[[可逆圧縮]]アルゴリズムの圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在することが、鳩の巣原理を用いて証明できる。具体的には下記の通り<ref name="Bell8">{{Cite conference2|language=en|url=https://books.google.com/books?id=exicCgAAQBAJ&pg=PA9|editor-last=Brodnik|editor-first=Andrej|editor2-last=Vahrenhold|editor2-first=Jan|last=Bell|first=Tim|author-link=ティム・ベル|book-title=Informatics in Schools. Curricula, Competences, and Competitions|conference=8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives|title=Surprising Computer Science|publisher=Springer|date=28 September 2015|volume=9378|pages=8–9|doi=10.1007/978-3-319-25396-1|isbn=978-3-319-25396-1|s2cid=26313283}}</ref><ref>{{Cite book2|language=en|title=Lossless Compression Handbook (Communications, Networking and Multimedia)|page=41|date=18 December 2002|editor-first=Khalid|editor-last=Sayood|edition=1st|publisher=Academic Press|isbn=978-0-12390754-7}}</ref>。
#「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
#圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする（MとNの単位は[[ビット]]）。
#圧縮処理後にデータサイズが小さくなるため、N < Mである。さらに圧縮処理後にデータサイズが大きくなる入力データが存在しないため、Nビットのデータは圧縮処理後もNビットとなる。
#Nビットのデータは2<sup>N</sup>種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2<sup>N</sup>+1種類存在する。
#しかしNビットのデータが2<sup>N</sup>種類しかないので、'''鳩の巣原理'''により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能（どちらに戻すべきか判別できない）である。
#したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」（可逆圧縮アルゴリズムではない）か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。

== 鳩の巣原理の一般化 ==
鳩の巣原理を一般化する。''n'' 個の離散的な対象を ''m'' 個の入れ物に割り当てるとすると、少なくとも1個の入れ物には、<math>\lceil n / m \rceil</math> 個より少なくない対象が割り当てられている。ここで <math>\lceil x \rceil</math> は[[床関数|天井関数]]のことであり、''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羽以上の鳩に占められる確率は、

:<math>1 - \frac{m(m-1)\cdots(m - n + 1)}{m^n} = 1 - \frac{m_{(n)}}{m^n},</math>

ただし、''m''<sub>(''n'')</sub> は[[下降階乗冪]]。''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% である。この問題は、もっと十分な長さでは、[[誕生日のパラドックス]]で扱われている。

==脚注==
{{Reflist}}

== 関連項目 ==
*{{ill2|組合せ数学の原理|en|Combinatorial principles}}
*[[濃度 (数学)]]
*[[ラムゼーの定理]]
*[[誕生日のパラドックス]]
*[[植木算#平面植木算・空間植木算|平面植木算・空間植木算]]

{{Normdaten}}
{{DEFAULTSORT:はとのすけんり}}
[[Category:数学の原理]]
[[Category:組合せ論]]
[[Category:代数学]]
[[Category:ラムゼー理論]]
[[Category:ペーター・グスタフ・ディリクレ]]
[[Category:数学に関する記事]]