鳩の巣原理（ディリクレの箱入れ原理）

鳩の巣原理（単射バージョン）

\(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 princple）などと呼びます。

鳩の巣原理（全射バージョン）

\(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\)への任意の写像が全射にはなり得ないことが明らかになりました。

鳩の巣原理の一般化

実数\(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）と呼びます。

天井関数を用いるとハトの巣原理をより一般的な形で表現できます。いくつか具体例を提示した上で、後に結果を一般化します。

以上を踏まえた上で、以下の命題が成り立つことを示します。

演習問題