アニヲタWiki(仮)
アニヲタWiki(仮)

ディリクレの箱入れ原理

登録日：2013/10/11 Fri 10:13:52
更新日：2023/12/19 Tue 22:47:35
所要時間：約 16 分で読めます


突然だが、主人公とヒロイン3人は世界の破滅を企むボスの野望を阻止すべく、
ボスの潜むダンジョンを駆け抜けていた！！！

主人公「よし、この先を抜ければボスのいる場所に着くはずだ！」

ヒロインA「今度こそ、今度こそあの人(ボス)を倒して世界を、祖国を救わなくては・・・」

ヒロインB「へへ、ボクと主人公クンがいればバッチリ安心モーマンタイさ！」

ヒロインC「あらあら～私もお忘れなきよう～」

ﾀｯﾀｯﾀ

ヒロインB「あれぇ！？道が分かれちゃってるよー！！！」

なんとそこには3つに分かれた道があった！！！

ボスの声「くっくっく、貴様らに朗報だ。その通路の先にはそれぞれワシのとびきり優秀な配下が3人待っておる。」

突然、響き渡るボスの声に驚く一同！！！！

ボスの声「そして、その3人を倒し1分以内に同時にスイッチを押さねばワシのいる場所へと繋がる道は現れぬのだよ…ワーハッハッハ！！！！」

主人公「な、なんだってぇ！？」

突然のご都合展k・・・げふんげふん敵の罠に驚愕する主人公一同！！！！

ボスの声「クックック、せいぜい頑張ることだな。期待してこの玉座で待っておるぞ！」

ヒロインC「これは～どうやら、私達は3つに分かれて進まないといけないようですねぇ～」

ヒロインB「う～ん、となるとボク達3人が分かれるとして…主人公クンどーしよっか。」

ヒロインA「それでは、主人公さんは私達の内誰と一緒に行くかを選んでください。これは大事な選択です、よーく考えて選んでくださいね？」

主人公(どーすんだよこれ・・・)

という訳で突然の修羅場になった主人公！！！！
一体誰の好感度を上げ・・・じゃなかった誰と一緒に行くのか！？
そして、やたら説明口調で主人公の好感度上げのためだけにめんどくさい罠を用意してくれる親切なボスを倒せるのだろうか！？

その答えは誰も知らない。

To be continued...


・概要
ディリクレの箱入れ原理とは、
ディリクレ（Johann Peter Gustav Lejeune Dirichlet；1805–1859)というドイツのえらーい数学者のおっちゃんが
1834年にSchubfachprinzip(「引き出し原理」)の名前で書いたと信じられている原理である。
別名を「鳩の巣原理」といい、日本ではこちらの方が名称として親しまれている(気がする)。

まずは小難しい書き方でざっくりと原理を説明してみよう。
「n 個の物を m 個の箱に入れるとき、n > m であれば、2個以上の物を含む箱が存在する」
より数学的な表現をすれば、
「任意の有限集合X, Yと写像f:X→Yについて, #X > #Y ならば a, b∈Xで a ≠ b かつ f(a) = f(b) なるものが存在する」
となる。(#Aは有限集合Aの元の個数を表す。高校数学ではn(A)と書くことが多い)

nとかmとか書かれててもわかんねーんじゃ(#ﾟДﾟ)ｺﾞﾙｧ!!という方もいらっしゃると思うので具体例を出そう。
まず、冒頭の如何にもファンタジーRPGの例を見て欲しい。
この例では4人のパーティがダンジョンを進んでいたら突然三叉路が現れて、
しかも3つ同時に攻略しなければいけなくなってしまった場面だ。(RPGにはよくあるテンプレ的な展開であるとは言ってはいけない)

この場合パーティ4人が同時に攻略しなくてはいけない箇所は3つであり、
その際必ずどこか1つには2人以上で進まなくてはいけなくなってしまったという訳だ。

他にも次のような例を挙げることができる。
ex.1)鳩の巣の例
鳩のために鳩の巣を9個作った。するとそこに10羽の鳩がやって来て巣へと入っていった。
しかし、鳩の数に対して巣の数が多いため少なくとも1つの巣には2匹以上の鳩がいることになる。
(これがもし♂と♀の巣であったら数ヶ月後にはまた数羽鳩が増えて小屋を足さないといけなくなるだろう。)

ex.2)野球チームの例
市内には4つの野球チームがあり、5人の子供が市内の野球チームに入りたいと思っている。
しかし、この5人の子供は互いに仲が悪く一緒のチームには入りたくない。
ところが市内にはチームが4つしかないため、仲の悪い5人の内2人は必ずどこかのチームに一緒に入らなくてはいけなくなってしまう。
(もしくは、一緒にプレイしたくない一心で野球やんなくてもいいやと思い始めるかもしれない。
こうして今日もまた一人将来の名プレイヤー候補が消えて行くのである。)

つまり、ディリクレの箱入れ原理とは
要は「入れられるモノが入れモノよりも多い場合には、必ずどれかの入れモノの中に入れられるモノがダブってしまう」と言っているに過ぎないのだ。

というか、上記の例はどれも当たり前すぎて、
「こんなんで原理とか呼んじゃっていいの！？」とふつーなら思ってしまいかねない原理である。

ところがぎっちょん、この原理は数学のある特定の領域の問題を解くのにとてつもない威力を発揮するすっげー原理なのである。
その威力たるや、かの背理法・帰納法に引けを取らないレベルの強力さであるということを強調しておこう。

また、この原理を一般化すると「ラムゼーの定理」という定理になる。

・ディリクレの箱入れ原理のすごさ
ディリクレの箱入れ原理のすごさを説明するために、ディリクレの箱入れ原理が使われる問題を紹介しよう。
おそらく、ディリクレの箱入れ原理で一番有名なのは「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」という以下の証明だろう。 

証明
ふつう、人間の髪の毛の本数は15万本ほどであるから、明らかに100万本以上の髪の毛を持っている人間はいないと考えることができる。
ロンドンの人口は100万を超える。もし、例えば「30万本の髪の毛の人用の箱」のように髪の毛の本数ごとに箱を割り当て、
箱にロンドンの人々を髪の毛の数に応じて割り当てるなら、
（当然の下限である0本から上限として置いた99万9999本までの箱に100万を超える人々を割り当てるのだから）
少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。

ん？なんか狐につままれたような気分だって？そりゃそうだろう。
それはこの証明の面白い特徴が原因となっている。

そもそもこの証明では、「同じ本数の髪の毛の人が存在すること」を証明しているにもかかわらず、
「具体的にどの2人が同じ本数の髪の毛を持ち、その本数が何本なのかは分からない」のである。
言ってしまえば「ロンドンに同じ本数の髪の毛を持った少なくとも2人の人間が存在するんだよ、いるいる！それは確かなんだ！ま、それが誰と誰で何本かは知ったこっちゃ無いんだけどねー(ゲス顔」と言われているようなものだ。
つまり、上記の証明では、ある性質を持つ物の存在を証明できても、その性質がどのような物であるかを知ることができないのだ。
そりゃ気持ちも悪いだろうし、頭では分かっても納得しにくいだろう。

しかし、これは逆にとてつもなく強力な性質であり、「存在さえ分かればいいや」という問題に対する有効な手段となるのだ。
例えばだが先ほどのロンドンの髪の毛の例を少しいじくって考えてみよう。

もし、どの人とどの人の髪の毛の数が同じでその本数は何本かを知りたいのであれば、
100万人の人達をいちいちチェックしなくてはならない上に、これは揚げ足取りだがもしかすると抜け毛や剃毛で髪の毛の数が1分1秒後に変化しかねない。
これが100万人のロンドンならばまだいい。しかし現代のロンドンには800万人近い人間が住んでいる。
これらを全部チェックするのか？と言われたらチェックできるわきゃねーだろ！！！というのが本音である。

また、これがロンドンという都市だけでなく世界各地のあらゆる国の都市について同じ調査をしないといけなくなったらどうだろう？
現実的な時間では決して解けない規模の問題となってしまうのは明白である。

しかし、存在だけ示せばいいのなら、上述のロンドンの例を拡張して「100万以上の人口を持つ都市には誰かは知らないが同じ本数の髪の毛を持った人間が存在する」と言ってしまえばいい。
これで証明は完了。無駄な労力を割く必要は一切なくなる。

実は問題の規模が大きくなればなるほど、実際の性質はどうでもよくなることが多い。
それよりもむしろ、具体的な性質までは知らなくていいから存在するかどうかだけをはっきりとさせたいという要求が多くなる。
(特に「無限」が登場する世界においてその傾向は顕著となる。)

そこで登場するのが存在性の証明であり、存在性の証明において非常に強力なツールとなるディリクレの箱入れ原理なのである。

元々は「入れられるモノが入れモノよりも多い場合には、必ずどれかの入れモノの中に入れられるモノがダブってしまう」だけの
「こんなんで原理とか呼んじゃっていいの！？」という感じだったディリクレの箱入れ原理がいつの間にかすごいものに思えてきたかもしれない。
実際筆者も数学をちょっとかじった時にこのディリクレの箱入れ原理を聞いて目を丸くしたものだった。
一見当たり前のように思える原理が、実は非常に強力な性質を持った原理であるというギャップ。そして面白さ。
ディリクレの箱入れ原理のすごさがこの項目を読んでくださっている皆様に少しでも伝わってくれれば、と願わずにはいられない。

なお、この原理は非常に強力であるため、大学入試などでこれを使いこなせるだけで解ける問題の幅は一気に広がる。
…しかし、しかしである。このディリクレの箱入れ原理、実は使いこなすのがひっじょーに難しい原理なのである。

・ディリクレの箱入れ原理のむずかしさ
多くの場合、人間の感覚的に単純な原理ほど使いこなすのは難しいものらしく、ディリクレの箱入れ原理もどう用いたらよいかがわかりにくいことが多い。

というのも、何が「入れられる物(箱)」で何が「箱に入れる物」なのかを決めるのが非常に難しいことに由来する。
以下の問題を解いてみて欲しい。ディリクレの箱入れ原理の適用の仕方の難しさが垣間見れるはずだ。

問題1
「タンスの中に片方ずつぐっちゃぐちゃになった白と黒の靴下(左右の区別はナシ)が20個ずつ入っている。今あなたは暗闇の中でそれを手探りで探している状態だ。
このとき最低何個の靴下をタンスから引っ張り出せば同じ色の靴下を揃えることができるだろうか？」

問題2
「1から10までの整数の中から相異なる6個の整数を選ぶと、それらの中には和が11になる2数が必ず含まれている。これを証明せよ。」

どちらも何が「入れられる物(箱)」で何が「箱に入れる物」かが分かれば一瞬だが、そうは問屋が卸さない。
答えはステルスにしておくので、見たい方はご覧ください。

問題1答え
答え：3個
箱として、
箱1：白い靴下が入る箱
箱2：黒い靴下が入る箱
を用意する。すると、ディリクレの箱入れ原理(鳩ノ巣原理)から靴下が3個以上のときに箱1と箱2のいずれかが2個＝色の揃った(1足の)靴下となる。

問題2答え
証明
1～10までの整数で、足して11になる組み合わせは(1,10)(2,9)(3,8)(4,7)(5,6)の5種類である。
これらを箱として用意すると、
ディリクレの箱入れ原理(鳩ノ巣原理)から6つ以上の相違な整数を選ぶときに5つの箱のいずれかに2つ以上の数字が入る(すなわち足して11になる)。

かなり簡単だが、「箱」の捉え方がうまくいかなかった方は苦戦を強いられたに違いない。
これらはまだ簡単な方だが、幾何学を組み合わせてみたりと、とにかく「どれを箱に選んだら良いか」がわかりづらく、色々とおつむがオーバーヒートしかねない問題が多い。
もし興味が有る方がいらしたら、是非「ディリクレの箱入れ原理」「鳩の巣原理」でググっていただきたい。
たぶんいくらでも例が出てくるはずである。


・ディリクレの箱入れ原理(おまけ)
さて、最後にロンドンの髪の毛の例と同じくらい有名な問題として、
ディリクレの箱入れ原理を一般化したラムゼーの定理におけるR2(3,3)=6の証明を紹介してこの項目を締めくくろうと思う。

R2(3,3)=6とか言われてもナンノコッチャと思うこと請け合いなので、R2(3,3)=6を分かりやすく言い換えると以下のようになる。

「世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる。」

え？どっかで聞いたことがあるだって？？もしかしてそれはスモール・ワールド現象(六次の隔たり)というヤツではないだろうか？
同じ6人という数字がキーワードとなるが、ソレとコレとは話が別なので気になる人は別途調べてみて欲しい。

という訳で、上記の命題の証明に移ろう。
世界中からランダムに6人を集めてくる、ということなのでてきとーに以下の6人を呼んでみよう。
(以下の6人が気に食わないという人はAさんBさんCさんDさんEさんFさんなり、おそ松カラ松チョロ松一松十四松トド松なり、六神ロボなり好きなモノに置き換えてください)

(´･ω･`)

( ＾ω＾)

('A`)

J('-`)し

<`∀´>

(　ﾟ∀ﾟ)

この6人の中に知り合いか知り合いでない3人組がいるかを証明しなくてはならないのだが、
いきなり6人の内から3人を取り出す場合だから、組み合わせの公式使って6C3=20通りで・・・とかやって、
6人の内2人の関係6C2=15通りに対して2^15=32768通りのパターンを考えてその全てのパターンで
上記の20通りの中に必ず知り合いか知り合いでない3人組がいることを証明してもいいが、
んなもん現実的に解ける量でないのは明白だろう。
32768通りのパターン考えて20通りに当てはまるか確認するとか紙何枚とどんだけの時間を使う気だ一体。

この場合ポイントは「知り合いか知り合いでない3人組がいるか」という存在の証明であり、
「一体誰と誰が具体的に知り合い・知り合いじゃないか」は知ったこっちゃないという点である。

具体的に誰が誰と知り合いでも知り合いじゃなくてもいいということはつまり、
「てきとーな誰か1人から見た世界の中には互いに知り合いか互いに知り合いじゃないのが3人いる」というのを発見できればいい。

ここではまず、ある人物から見た時の知り合いか知り合いじゃないかの関係を見てみよう。
そこで代表者として(´･ω･`) を選択しよう。

そして2つの箱を作る。
箱1：「(´･ω･`)と知り合い同士の人が入る箱」
箱2：「(´･ω･`)と知り合い同士でない人が入る箱」
すると、ディリクレの箱入れ原理から、5つのモノを2つの箱にどう分けたとしても必ずどちらかの箱には3つ以上入ってしまうことが分かる。
実際に書いてみると以下のようになるのが分かる。 
例)
箱1：5人　箱2：0人　
箱1：4人　箱2：1人　
箱1：3人　箱2：2人　
↑知り合いが必ず3人以上↑
↓知り合いじゃないのが必ず3人以上↓
箱1：2人　箱2：3人　
箱1：1人　箱2：4人　
箱1：0人　箱2：5人　

つまり(´･ω･`)から見たら、というか誰から見ても必ず3人は知り合いか知り合いじゃないという事になる。
これで証明完了…と行きたいところだが、コレでは不十分だ。

というのも、問題文は「互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組」であり、
(´･ω･`)の知り合いもしくは知り合いじゃない人間が2人いても、その2人が知り合いもしくは知り合いじゃないと求めていた3人組にはならないのだ。 
例)
(´･ω･`) と ('A`) は知り合い(or知り合いじゃない)
(´･ω･`) と J('-`)し は知り合い(or知り合いじゃない)
だとしても
('A`) と J('-`)し は知り合いじゃない(or知り合い)
の可能性がある。

更に言うならたとえ(´･ω･`)の知り合い3人が互いに知り合いじゃなくても知り合いであっても求めていた3人組になる。 
例)
(´･ω･`) と ('A`) は知り合い(or知り合いじゃない)
(´･ω･`) と J('-`)し は知り合い(or知り合いじゃない)
(´･ω･`) と <`∀´> は知り合い(or知り合いじゃない)
だとしても
('A`) と J('-`)し と <`∀´> はお互いに知り合いじゃない(or知り合い)
である可能性がある。


とりあえず、(´･ω･`)と知り合いもしくは知り合いでない同士の3人をここに呼んでみよう。

( ＾ω＾) おっお！
<`∀´> ﾆﾀﾞｰ!!
(　ﾟ∀ﾟ) ｷﾀｰ!!
(もちろん本当は誰だって構わない)

実は、この(´･ω･`), ( ＾ω＾), <`∀´>, (　ﾟ∀ﾟ) の4人の中から求めるべき3人組を見つけられるのだ。
ここから場合分けをして考える。今、次のどちらか片方のみが成り立っている。
(1) ( ＾ω＾), <`∀´>, (　ﾟ∀ﾟ)の全員が(´･ω･`)と知り合い。
(2) ( ＾ω＾), <`∀´>, (　ﾟ∀ﾟ)の誰も(´･ω･`)と知り合いでない。

まず(1)の方から考える。このとき、次の4つのうちどれか一つのみが成り立っている。
(1-1) ( ＾ω＾)-<`∀´>が知り合いである場合。<`∀´>-(　ﾟ∀ﾟ)と(　ﾟ∀ﾟ)-( ＾ω＾)の関係は問わない。
(1-2) ( ＾ω＾)-<`∀´>が知り合いでなく、<`∀´>-(　ﾟ∀ﾟ)が知り合いである場合。(　ﾟ∀ﾟ)-( ＾ω＾)の関係は問わない。
(1-3) ( ＾ω＾)-<`∀´>が知り合いでなく、<`∀´>-(　ﾟ∀ﾟ)が知り合いでなく、(　ﾟ∀ﾟ)-( ＾ω＾)知り合いである場合。
(1-4) ( ＾ω＾)-<`∀´>が知り合いでなく、<`∀´>-(　ﾟ∀ﾟ)が知り合いでなく、(　ﾟ∀ﾟ)-( ＾ω＾)が知り合いでない場合。

(1-1),(1-2),(1-3)ではいずれの場合も知り合いである二人に(´･ω･`)を加えれば互いに全員知り合いである3人組になる。
(1-4)では(´･ω･`)以外の3人が互いに全く知り合いでない3人組になる。
よって(1)の場合には求めていた3人組が作れることが分かった。

次に(2)の場合を考えなければならないが、
今度は「知り合いである」と「知り合いでない」を入れ替えれば全く同様の議論ができることが分かる。
(1-1),(1-2),(1-3),(1-4)の「知り合いである」と「知り合いでない」を入れ替えた条件を(2-1),(2-2),(2-3),(2-4)とすると
(2-1),(2-2),(2-3)ではいずれの場合も知り合いでない二人に(´･ω･`)を加えれば互いに全く知り合いでない3人組になるし、
(2-4)は(´･ω･`)以外の3人が互いに全員知り合いの3人組になる。


という訳で結局、
「世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる。」
が証明された。

・鳩の巣原理自体の証明
ここまでは鳩の巣原理を使って証明できる命題の例をいくつか挙げた。次にこの原理そのものの証明を考えてみよう。冒頭の鳩の巣原理の主張を確認する。
「任意の有限集合X, Yと写像f:X→Yについて, #X > #Y ならば a, b∈Xで a ≠ b かつ f(a) = f(b) なるものが存在する」
このことは背理法によって次のように証明される。
まず
「#X > #Yを満たす有限集合X, Yについて, 写像f:X→Yで「a ≠ b (a, b∈X) ならば f(a) ≠ f(b)」を満たすものが存在する」
と仮定してみよう. このとき, 任意の y∈f(X) に対し, f(x)=y となる x∈X がただ1つ存在している. したがって, #f(X) = #X が成り立っている.
さらに, 仮定より#X > #Y だから #f(X) > #Y となるが, f(X)⊂Yより#f(X) ≦ #Y だからこれは矛盾. これより鳩の巣原理が示された.

これでは難しいという人のために鳩の巣の比喩を使ってこの証明を説明すると次のようになる。
鳩が何羽かいる. 鳩の巣も何個かある. 鳩の総数は鳩の巣の総数より多い. この状況下で全ての鳩をそれぞれいずれかの鳩の巣に入れていく.
全ての巣に多くても1羽しかいないと仮定してみよう. このとき, 少なくとも1羽の鳩が入っている鳩の巣には必ず鳩がちょうど1羽入っている. したがって, 「鳩の数」=「鳩が入っている鳩の巣の数」となっている. 仮定より「鳩の数」>「鳩の巣の数」だから「鳩が入っている鳩の巣の数」>「鳩の巣の数」となるが, どう考えても「鳩が入っている鳩の巣の数」≦「鳩の巣の数」だからこれは矛盾.

この比喩は先程の証明において X ～ 鳩全体, Y ～ 鳩の巣全体, f ～ 鳩の入れ方, f(X) ～ 鳩が入っている鳩の巣全体 としたものである。そう思って読めば先の証明も簡単に見えてくるのではないだろうか。

・無限集合の場合
再び鳩の巣原理の主張を確認しよう。
「任意の有限集合X, Yと写像f:X→Yについて, #X > #Y ならば a, b∈Xで a ≠ b かつ f(a) = f(b) なるものが存在する」
ここではXとYは有限集合としているが、もしX,Yの少なくとも一方が無限集合ならどうなるだろうか、という疑問を持つのは自然だろう。
このときには以下の3つの場合がある。

場合1:Xが有限集合, Yが無限集合
場合2:Xが無限集合, Yが有限集合
場合3:XもYも無限集合

とはいえ、場合1なら #X > #Y になるはずがないので, 我々が考えるべきは場合2と場合3の2つである。
場合2は無限にいる鳩を有限個しかない鳩の巣に入れようとする状況を考えればほとんど明らかである。きちんと証明する場合も先程の有限の場合の証明と同じようにできる。
一方で、場合3の場合は困ったことになる。そもそもX,Yが無限集合の場合に#X > #Yという不等式が何を意味するのだろうか？ということを考えなくてはならないからだ。結論から言うと、X,Yが無限集合の場合にも#X > #Yという不等式を考えることができ、しかも鳩の巣原理の主張は正しい。
現代数学においては、無限集合の「元の個数」の大小は次のように定義されている。

(1) 写像f:X→Yで「a ≠ b ならば f(a) ≠ f(b)」かつ「任意の y∈Y に対し f(x) = y となる x∈X」が成り立つものが存在するとき, #X = #Y と定義する.
(2) (1)の条件が成り立たないとき, #X ≠ #Y と定義する.
(3) 写像f:X→Yで「a ≠ b ならば f(a) ≠ f(b)」が成り立つものが存在するとき, #X ≦ #Y と定義する.
(4) #X ≦ #Y かつ #X ≠ #Y のとき, #X < #Y と定義する.

難しい定義に思えるかもしれないが、このように定義すると有限集合の場合と同様の方法で鳩の巣原理の主張を証明することができる。というより、この定義は「無限集合の場合でも鳩の巣原理が成り立つ」ようにできているのだ。現代の数学というものは一見難解だが実際には簡単な場合の自然な拡張となっていることが多い。これはその例の1つである。


・余談
蒼柳碧人の小説「浜村渚の計算ノート」では、浜村渚が「鳩の巣原理」を「元から巣の中にいた鳩が、新しく来た2羽目の鳩を追い返したりはしない」事に基づいた、とても優しい原理であると語っている。

現実世界では物理的に２羽目が入れないことだってあるだろうが、数学的には相手を無下に追い返したりはしないのである。我々も見習いたいところである。

追記・修正は自分と頭髪の本数が同じ人が存在する人にお願いします。


この項目が面白かったなら……＼ポチッと/

▷ コメント欄

タグ：

数学 なるほど、わからん 鳩の巣原理 ディリクレの箱入れ原理 ディリクレ
+ タグ編集
  • タグ：
  • 数学
  • なるほど、わからん
  • 鳩の巣原理
  • ディリクレの箱入れ原理
  • ディリクレ

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー と 利用規約 が適用されます。

タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「ディリクレの箱入れ原理」をウィキ内検索
最終更新：2023年12月19日 22:47