|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 箱 ： [はこ] 【名詞】 1. box ・ 入 ： [にゅう] 【名詞】 1. go in ・ 入れ ： [いれ] 1. (n-suf) container 2. receptacle ・ 原 ： [はら, もと] 1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation ・ 原理 ： [げんり] 【名詞】 1. principle 2. theory 3. fundamental truth ・ 理 ： [り] 【名詞】 1. reason
鳩の巣原理（はとのすげんり、）またはディリクレの箱入れ原理（ディリクレのはこいれげんり、）、あるいは部屋割り論法とは、''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万を超える。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てるなら、（当然の下限である0本から上限として置いた99万9999本までの巣に100万を超える人々を割り当てるのだから）少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。 もう1つのきわめて有名な例は、世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる、というものである。詳細は、ラムゼーの定理および組合せ数学のラムゼー理論の項を参照。 鳩の巣原理は、計算機科学の分野ではしばしば現れる。たとえば、ハッシュテーブルでは、通常利用されるキーの種類は配列のインデックスの取りうる値の数を上回ることから、ハッシュ値の衝突は避けられない。この衝突を回避できるハッシュアルゴリズムが存在しえないことは、この原理によって証明されている。また、どんな可逆圧縮アルゴリズムも特定のデータに対しては、元よりもデータ量の大きな形に変換せざるを得ない。「圧縮」アルゴリズムである以上、あるnバイトの元データを(n-1)バイト以下に変換できるはずであるが、このとき、元々(n-1)バイト以下である 2n-1 種類の元データのうち少なくとも1つをnバイト以上に変換するようにしなければ、2n 種類の元データを 2n-1 通りのデータに変換することになる。鳩の巣原理により、少なくとも1つの変換後データは2つ以上の元データに対応することになり、伸張はどうなるのか不明になってしまう。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「鳩の巣原理」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Pigeonhole principle 」があります。 スポンサード リンク
|