鳩の巣原理（単射バージョン）
\(n\)羽のハトが\(m\)個の巣の中に入っているものとします。ただし、\(n,m\)は自然数かつ\(n>m\)であるものとします。つまり、ハトの数が巣の数よりも多いということです。この場合、少なくとも1つの巣には複数のハトが入っているはずです。
以上の主張を集合論の言語を用いて改めて表現します。すべてのハトからなる集合を\(A\)で、すべての巣からなる集合を\(B\)でそれぞれ表記します。\(A,B\)はともに有限集合であるとともに、それらの濃度について\(\left\vert A\right\vert >\left\vert B\right\vert \)が成り立つものとします。その上で、それぞれのハト\(a\in A\)に対して、そのハトが入っている巣穴\(f\left( a\right) \in B\)を特定する写像\(f:A\rightarrow B\)を定義します。この場合、少なくとも1つの巣穴\(b\in B\)に異なるハト\(a,a^{\prime }\in A\)が入っており、したがって、\begin{equation*}a\not=a^{\prime }\wedge f\left( a\right) =f\left( a^{\prime }\right) =b
\end{equation*}が成り立ちますが、これは\(f\)が単射ではないことを意味します。ハトが入っている巣を入れ替えても、すなわち\(A\)から\(B\)への写像を任意に選んだ場合でも同様の議論が成立するため、\(A\)から\(B\)への任意の写像が単射にはなり得ないことが明らかになりました。これを鳩の巣原理（pigeonhole principle）やディリクレの箱入れ原理（Dirichlet’s box principle）などと呼びます。
単射型の鳩の巣原理は、同じ分類先に入る複数の対象が存在することを示す上で有用です。以下が具体例です。
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。\(A,B\)の定義より、\begin{equation*}\left\vert A\right\vert =27>26=\left\vert B\right\vert
\end{equation*}であるため、鳩の巣原理より\(f\)は単射ではありません。つまり、少なくとも2つの英単語が同じ頭文字を持ちます。
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。その上で、\begin{equation*}
\left\vert A\right\vert >\left\vert B\right\vert
\end{equation*}すなわち、\begin{equation*}
\left\vert A\right\vert >101
\end{equation*}すなわち、\begin{equation*}
\left\vert A\right\vert \geq 102
\end{equation*}が成り立つ場合、鳩の巣原理より\(f\)は単射ではなく、ゆえに複数の受験者が同じ得点をとります。
\end{equation*}の\(n\)通りですが、これらの余りからなる集合を\(B\)で表記します。それぞれの整数\(a\in A\)に対して、\begin{equation*}f\left( a\right) =a\text{を}n\text{で割った余り}\in B
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。\(A,B\)の定義より、\begin{equation*}\left\vert A\right\vert =n+1>n=\left\vert B\right\vert
\end{equation*}であるため、鳩の巣原理より\(f\)は単射ではありません。つまり、少なくとも2つの整数が同じ余りを持ちます。
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。ただし、分割線上にある点については、それが接する小正方形のうちの1つに、あらかじめ定めた規則にしたがって対応させるものとします。\(A,B\)の定義より、\begin{equation*}\left\vert A\right\vert =5>4=\left\vert B\right\vert
\end{equation*}であるため、鳩の巣原理より\(f\)は単射ではありません。つまり、少なくとも2つの点が同じ小正方形に属します。具体的には、一辺の長さが\(\frac{1}{2}\)である小正方形内の2点間の距離は、その小正方形の対角線の長さ\begin{equation*}\sqrt{\left( \frac{1}{2}\right) ^{2}+\left( \frac{1}{2}\right) ^{2}}=\frac{\sqrt{2}}{2}
\end{equation*}以下であるため、5個の点の中には、距離が\(\frac{\sqrt{2}}{2}\)以下であるような複数の点が存在します。
鳩の巣原理（全射バージョン）
\(n\)羽のハトが\(m\)個の巣の中に入っているものとします。ただし、\(n,m\)は自然数かつ\(n<m\)であるものとします。つまり、先とは異なり、巣の数がハトの数より多いということです。この場合、少なくとも1つの巣が空いているはずです。
以上の主張を集合論の言語を用いて改めて表現します。すべてのハトからなる集合を\(A\)で、すべての巣からなる集合を\(B\)でそれぞれ表記します。\(A,B\)はともに有限集合であるとともに、それらの濃度について\(\left\vert A\right\vert <\left\vert B\right\vert \)が成り立つものとします。その上で、それぞれのハト\(a\in A\)に対して、そのハトが入っている巣穴\(f\left( a\right) \in B\)を特定する写像\(f:A\rightarrow B\)を定義します。この場合、少なくとも1つの巣穴\(b\in B\)が空いており、したがって、それに対して、\begin{equation*}b=f\left( a\right)
\end{equation*}を満たす\(a\in A\)は存在しませんが、これは\(f\)が全射ではないことを意味します。ハトが入っている巣を入れ替えても、すなわち\(A\)から\(B\)への写像を任意に選んだ場合でも同様の議論が成立するため、\(A\)から\(B\)への任意の写像が全射にはなり得ないことが明らかになりました。
全射型の鳩の巣原理は、少なくとも1つの分類先が使われないことを示す上で有用です。以下が具体例です。
\end{equation*}の\(n+1\)通りですが、これらの余りからなる集合を\(B\)で表記します。それぞれの整数\(a\in A\)に対して、\begin{equation*}f\left( a\right) =a\text{を}n+1\text{で割った余り}\in B
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。\(A,B\)の定義より、\begin{equation*}\left\vert A\right\vert =n<n+1=\left\vert B\right\vert
\end{equation*}であるため、鳩の巣原理より\(f\)は全射ではありません。つまり、選ばれたどの整数の余りにならないものが少なくとも1つ存在します。
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義します。\(A,B\)の定義より、\begin{equation*}\left\vert A\right\vert =7<8=\left\vert B\right\vert
\end{equation*}であるため、鳩の巣原理より\(f\)は全射ではありません。つまり、どの学生にも選ばれない研究テーマが少なくとも1つ存在します。
鳩の巣原理の一般化
実数\(x\in \mathbb{R} \)が与えられたとき、\(x\)以上の最小の整数を、\begin{equation*}\left\lceil x\right\rceil =\min \left\{ z\in \mathbb{Z} \ |\ x\leq z\right\}
\end{equation*}で表記します。定義より、\begin{equation*}
\left\lceil x\right\rceil -1<x\leq \left\lceil x\right\rceil
\end{equation*}が成り立ちます。その上で、それぞれの実数\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =\left\lceil x\right\rceil
\end{equation*}を像として定める関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)を天井関数（ceiling function）と呼びます。
\left\lceil 1\right\rceil &=&\min \left\{ z\in \mathbb{Z} \ |\ 1\leq z\right\} =1 \\
\left\lceil 1.5\right\rceil &=&\min \left\{ z\in \mathbb{Z} \ |\ 1.5\leq z\right\} =2 \\
\left\lceil -1\right\rceil &=&\min \left\{ z\in \mathbb{Z} \ |\ -1\leq z\right\} =-1 \\
\left\lceil -1.5\right\rceil &=&\min \left\{ z\in \mathbb{Z} \ |\ -1.5\leq z\right\} =-1
\end{eqnarray*}などが成り立ちます。
天井関数を用いるとハトの巣原理をより一般的な形で表現できます。具体例を提示した上で、後に結果を一般化します。
\end{equation*}羽です。すべての巣に入る鳩の数が\(3\)羽以下ならば、ハトの総数は高々\(9\)羽となってしまいます。したがって、少なくとも１つの巣には、\begin{equation*}\left\lceil \frac{10}{3}\right\rceil =4
\end{equation*}羽以上のハトが入ります。
以上を踏まえた上で、以下の命題が成り立つことを示します。
一般化された鳩の巣原理は、同じ分類先に入る対象数の下限を具体的に評価する上で有用です。以下が具体例です。
\end{equation*}人以上が対応します。
\end{equation*}の\(n\)通りです。\(n+1\)個の整数をハト、\(n\)通りの余りを巣とみなすと、\begin{equation*}\left\lceil \frac{n+1}{n}\right\rceil =\left\lceil 1+\frac{1}{n}\right\rceil
=2
\end{equation*}が成り立つため、一般化された鳩の巣原理より、少なくとも2つの整数は同じ余りを持ちます。
先の命題を写像を用いて表現するとどうなるでしょうか。有限集合\(A,B\)について、\(A\)をハトの集合、\(B\)を巣の集合とみなします。さらに、写像\(f:A\rightarrow B\)はそれぞれのハト\(a\in A\)に対して、\begin{equation*}f\left( a\right) =a\text{が入っている巣}\in B
\end{equation*}を特定するものとします。先の命題より、少なくとも1つの巣\(b\in B\)には最低でも、\begin{equation*}\left\lceil \frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\end{equation*}羽のハトが入っています。巣\(b\)に入っているハトからなる集合は\(f\)による\(b\)の逆像\begin{equation*}f^{-1}\left( b\right) =\left\{ a\in A\ |\ f\left( a\right) =b\right\}
\end{equation*}であるため、\begin{equation*}
\exists b\in B:\left\vert f^{-1}\left( b\right) \right\vert \geq \left\lceil
\frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\end{equation*}を得ます。
\frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\end{equation*}が成り立つ。
\end{equation*}を特定する写像\begin{equation*}
f:A\rightarrow B
\end{equation*}に注目します。先の命題より、\begin{equation*}
\exists b\in B:\left\vert f^{-1}\left( b\right) \right\vert \geq \left\lceil
\frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\end{equation*}が成り立ちますが、\begin{equation*}
\left\lceil \frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil =\left\lceil \frac{100}{9}\right\rceil =12
\end{equation*}であるため、\begin{equation*}
\exists b\in B:\left\vert f^{-1}\left( b\right) \right\vert \geq 12
\end{equation*}を得ます。つまり、少なくとも1つのグループには\(12\)人以上の学生が所属します。
\frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\quad \cdots (1)
\end{equation}が成り立つことが明らかになりました。特に、\begin{equation*}
\left\vert A\right\vert >\left\vert B\right\vert
\end{equation*}である場合には、\begin{equation*}
\frac{\left\vert A\right\vert }{\left\vert B\right\vert }>1
\end{equation*}であるため、\begin{equation*}
\left\lceil \frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil \geq 2
\end{equation*}を得ます。すると\(\left(1\right) \)より、\begin{equation*}\exists b\in B:\left\vert f^{-1}\left( b\right) \right\vert \geq 2
\end{equation*}を得ます。これは、何らかの異なる\(a,a^{\prime }\in A\)に対して、\begin{equation*}f\left( a\right) =f\left( a^{\prime }\right) =b
\end{equation*}が成り立つことを意味します。つまり、\(f\)は単射ではないということです。これは単射型の鳩の巣原理の主張に他なりません。以上の議論より、一般化された鳩の巣原理は、単射型の鳩の巣原理の一般化であることが明らかになりました。両者の違いは、得られる評価の強さにあります。単射型の鳩の巣原理は、1つの分類先に少なくとも2個の対象が対応するという主張であるのに対し、一般化された鳩の巣原理は、1つの分類先に対応する対象数について、\begin{equation*}\left\lceil \frac{\left\vert A\right\vert }{\left\vert B\right\vert }\right\rceil
\end{equation*}という、対象と分類先の数に応じた具体的な下限を与えます。
演習問題
- \(f\)は単射である。
- \(f\)は全射である。
- \(f\)は全単射である。
