鳩の巣原理

鳩の巣原理の最新ニュースをまとめて検索！

現実の鳩の巣。ここでは（鳩に幸い）n = 7, m = 9。

鳩の巣原理（はとのすげんり）またはディリクレの箱入れ原理（—はこいれげんり）とは、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万以上である。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てれば、（約15万に100万以上を割り当てるのだから）少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。

もう1つのきわめて有名な例は、世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる、というものである。詳細は、ラムゼーの定理および組合せ数学のラムゼー理論の項を参照。

鳩の巣原理は、計算機科学の分野ではしばしば発生する。たとえば、ハッシュテーブルで、可能なキーの数は配列のインデックスを上回るから、ハッシュ値の衝突は避けられない。いかにうまくしても、この衝突を回避できるハッシュアルゴリズムは存在しない。この原理はまた、可逆圧縮はある分量以上の圧縮ができない、ということも証明している。もしも2つのファイルが同じサイズまで小さく圧縮されたとしたら、解凍はどうなるのか不明になってしまう。

[編集] 存在性証明としての鳩の巣原理

前述した「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」事の証明の面白いところは、同じ本数の髪の毛の人が存在する事を証明しているにも関わらず、具体的にどの2人が同じ本数の髪の毛を持つのかは分からない事である。鳩の巣原理を使った証明にはこのような特徴をもつものが多く、何らかの性質を満たすものが存在する事を証明するにも関わらず、どれがその性質を満たすのかについては何も分からない。 もちろん100万人以上いるロンドン市民の髪の毛の本数を全員チェックすればどの２人が同じ本数の髪の毛を持つのか分かるが、このような非効率的な事をしなくても定理が証明できるのが鳩の巣原理の利点である。 (チェックが多項式時間でできないにも関わらず鳩の巣原理により存在性のみが言える例もある)。

この特徴の故、鳩の巣原理は定理を証明する強力な道具になる。 実際、無限がからんだ場合、鳩の巣原理を使わないとおよそ証明できない命題を証明できる場合がある。 前述の例を少しだけ改変して、「任意の都市Xに対し、Xには同じ本数の髪の毛を持った少なくとも2人の人間が存在する」という命題を考える。 世界にある都市の数が有限であれば、全ての都市にいる全ての人間の髪の毛の本数を数える事で上述の命題の真偽がチェックできるが、 都市の数が無限であれば、全ての都市についてチェックするのは原理的に不可能である。 しかし鳩の巣原理を使えば、たとえ都市の数が無限であってもこの定理が真である事を一瞬にして証明できる。

[編集] 鳩の巣原理の一般化

鳩の巣原理を一般化する。n 個の離散的な対象を m 個の容れ物に割り当てるとすると、少なくとも1個の容れ物には、 個より少なくない対象が割り当てられている。ここで は天井関数のことであり、x より等しいか大きい最小の整数を表す。

鳩の巣原理はさらに一般化され、グラフなどのより複雑な数学的構造、また算術的な関係などに対しても類似の定理が知られている（ラムゼーの定理など）。それらをラムゼー型の定理という。

[編集] 面積を使った一般化

Aをn元集合とし、Bをm元集合とし、fをAからBへの関数とする。 このときnがmより大きければ、鳩の巣原理よりfは単射ではありえない。

同様に平面上の集合Aの面積がxでBの面積がyであるとし、fをAからBへの連続関数(あるいは一般的に可測関数)とする。 このときxがyより大きければ、fは単射ではありえない。 (厳密に言うと、Aは可測集合(=面積の定義できる集合)である必要がある)。 面積を使ったこの論法はたとえば初等整数論におけるミンコフスキーの定理を証明するのに使われる。

後者の論法は前者の「連続版」とみなす事ができる。 (「総和」の連続版が「積分」であるようなもの)。 より数学的にいうと、後者の論法は測度空間上の論法に一般化でき、counting measureの場合が前者に一致する。

[編集] 確率を使った一般化

次に、確率的な一般化を述べる。n 羽の鳩が m 個のそれぞれの巣へ 1 / m の確率で入れられるとすると、少なくとも1つの巣が2羽以上の鳩に占められる確率は、

ただし、m_(n) は下方階乗冪。n = 0, 1（で m > 0）のとき、確率は0である。言い換えれば、鳩が1羽のとき、衝突は起こらない。n > m であれば（鳩が巣より多ければ）、通常の鳩の巣原理を使い、確率は1である。しかし、たとえ鳩が巣より少なかったとしても（n m でも）、巣への鳩の割当ての無作為性により、衝突が起こる可能性は十分にある。たとえば、少なくとも1つの巣が2羽以上の鳩に占められる確率は 25%。10個に5羽なら確率は 69.76% であり、20個に10羽なら 93.45% である。この問題は、もっと十分な長さでは、誕生日のパラドックスで扱われている。

[編集] 関連項目

• 組合せ数学の原理
• 濃度 (数学)
• ラムゼーの定理
• 誕生日のパラドックス