教材一覧
教材一覧
教材検索

集合の濃度

鳩の巣原理(ディリクレの箱入れ原理)

目次

次のページ:

無限集合

Twitterで共有
メールで共有

鳩の巣原理(単射バージョン)

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

命題(単射に関する鳩の巣原理)
集合\(A,B\)がともに有限集合であるとともに\(\left\vert A\right\vert >\left\vert B\right\vert \)が成り立つ場合には、\(A\)から\(B\)への単射は存在しない。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(ハトの巣原理)
\(27\)個の英単語の中には同じ頭文字を持つものが必ず存在します。なぜなら、アルファベットは全部で\(26\)種類だからです。実際、問題としている\(27\)個の英単語からなる集合を\(A\)で、すべてのアルファベットからなる集合を\(B\)でそれぞれ表記した上で、それぞれの英単語\(a\in A\)に対してその頭文字を\(f\left(a\right) \in B\)として定める写像\(f:A\rightarrow B\)を定義します。仮定より\(\left\vert A\right\vert >\left\vert B\right\vert \)であるため、鳩の巣原理より\(f\)は単射にはなり得ません。つまり、少なくとも2つの英単語が同じ頭文字を持つということです。
例(鳩の巣原理)
ある試験の最低点は\(0\)点、最高点は\(100\)であり、得点は整数だけを値としてとるものとします。つまり、試験の結果は全部で\(101\)通りです。少なくとも2人の生徒が同じ得点を取ることを保証するためには\(102\)人の受験者がいれば十分です。実際、すべての受験者からなる集合を\(A\)で、すべての得点からなる集合を\(B\)で、それぞれの受験者\(a\in A\)に対してその人が得た得点を\(f\left( a\right) \in B\)として定める写像\(f:A\rightarrow B\)を定義したとき、鳩の巣原理より\(\left\vert A\right\vert >\left\vert B\right\vert \)であれば\(f\)は単射になり得ず、したがって複数の受験者が同じ得点をとることになります。仮定より\(\left\vert B\right\vert =101\)であるため\(\left\vert A\right\vert \geq 102\)であれば条件が満たされます。

 

鳩の巣原理(全射バージョン)

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

命題(全射に関する鳩の巣原理)
集合\(A,B\)がともに有限集合であるとともに\(\left\vert A\right\vert <\left\vert B\right\vert \)が成り立つ場合には、\(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)と呼びます。

例(天井関数)
天井関数\(\left\lceil x\right\rceil :\mathbb{R} \rightarrow \mathbb{R} \)について、\begin{eqnarray*}\left\lceil \pi \right\rceil &=&\min \left\{ z\in \mathbb{Z} \ |\ \pi \leq z\right\} =4 \\
\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*}などが成り立ちます。

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

例(鳩の巣原理)
\(10\)羽のハトに対して\(3\)個の巣があるものとします。ハトをできるだけ分散させて入れると1つの巣に入るハトの数を\(\frac{10}{3}=3.33\)羽まで抑えることができますが、ハトを分割することはできないため、少なくとも1つの巣には最低でも\(\left\lceil3.33\right\rceil =4\)羽のハトが入っていることになります。
例(鳩の巣原理)
\(3\)羽のハトに対して\(6\)個の巣があるものとします。ハトをできるだけ分散されて入れると1つの巣に入るハトの数を\(\frac{3}{6}=0.5\)羽まで抑えることができますが、ハトを分割することはできないため、少なくとも1つの巣には最低でも\(\left\lceil0.5\right\rceil =1\)羽のハトが入っていることになります。

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

命題(鳩の巣原理の一般化)
\(n\)羽のハトが\(m\)個の巣の中に入っているものとする。ただし、\(n,m\in \mathbb{N} \)である。この場合、少なくとも1つの巣には最低でも\(\left\lceil \frac{n}{m}\right\rceil \)羽のハトが入っている。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(鳩の巣原理の一般化)
\(40\)人のヒトを任意に選んだとき、同じ月に産まれた人は最低でも\(4\)人います。実際、月は\(1\)月から\(12\)月までの\(12\)通り存在するため、これは\(40\)匹のハトを\(12\)個の巣の中に入れる状況に等しく、すると鳩の巣の原理より、少なくとも1つの月に関して、その月に誕生日である人が最低でも\(\left\lceil \frac{40}{12}\right\rceil =\left\lceil3.33\right\rceil =4\)人いることが保証されます。

 

演習問題

問題(鳩の巣原理)
\(1\)以上\(11\)以下の整数の中から\(7\)個の異なる整数を選んだとき、その中の何らかの\(2\)つの数の和が\(12\)になることを示してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(鳩の巣原理)
\(7\)個の異なる自然数を選んだとき、その中の何らかの\(3\)つの数の和が必ず\(3\)で割り切れることを示してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次のページ:

無限集合

Twitterで共有
メールで共有
DISCUSSION

質問とコメント