鳩の巣原理(ディリクレの部屋割り論法)

n個の鳩がm個の巣に入るとき、n > mならば少なくとも1つの巣には2羽以上の鳩が入る。より一般に、\(\lceil \frac{n}{m} \rceil\)以上の鳩が入る巣が存在する。

鳩の巣原理は、基本的ながら強力な組合せ論の原理で、有限集合の間の写像に関する重要な性質を示す。離散数学や計算機科学など、幅広い分野で応用される。

証明

鳩の巣原理を証明するために、まずn > mの場合を考える。すべての巣に高々1羽の鳩しか入らないと仮定すると、鳩の総数はm羽以下となるが、これはn > mに矛盾する。したがって、少なくとも1つの巣には2羽以上の鳩が入る。次に、一般の場合を考える。k = \(\lceil \frac{n}{m} \rceil\)とおく。各巣に高々(k-1)羽の鳩しか入らないと仮定すると、鳩の総数はm(k-1)羽以下となる。しかし、kの定義より\(k-1 < \frac{n}{m}\)なので\(m(k-1) < n\)となり、これは矛盾である。したがって、少なくとも1つの巣にはk羽以上の鳩が入る。これにより、鳩の巣原理が証明される。(証明終)

【応用例の説明】

例:366人の人がいれば、必ず同じ誕生日の組が存在する(365日を巣と見る)。

例:13枚のトランプを引けば、必ず同じスートが4枚以上含まれる(4スートを巣と見る)。

【無限集合への拡張】

無限集合に対しても、濃度を用いて一般化された鳩の巣原理が成立する。

例:実数から可算集合への写像は、少なくとも1つの逆像が非可算となる。