§B4.2鳩の巣原理

最終更新

有限個の対象を有限個の箱へ分類するとき、対象の個数が箱の個数より多ければ、鳩の巣原理により、同じ箱に入る異なる二つの対象が存在します。ただし、鳩の巣原理から分かるのは、そのような二つの対象が存在することだけであり、どの二つの対象が同じ箱に入るかは分かりません。

1 有限集合の間の写像

対象の集合をXX、箱の集合をYYとし、対象xxが入る箱をf(x)f(x)と書きます。

定義 1.1 (単射と全射). 写像f:X→Yf:X\to Yが単射であるとは、f(x1)=f(x2)f(x_1)=f(x_2)ならばx1=x2x_1=x_2が成り立つことをいいます。写像ffが全射であるとは、すべてのy∈Yy\in Yに対してf(x)=yf(x)=yを満たすx∈Xx\in Xが存在することをいいます。

鳩の巣原理を写像の言葉で述べます。

定理 1.2 (鳩の巣原理).X,YX,Yを有限集合とし、f:X→Yf:X\to Yを写像とします。∣X∣>∣Y∣|X|>|Y|ならばffは単射ではありません。したがって、異なるx1,x2∈Xx_1,x_2\in Xでf(x1)=f(x2)f(x_1)=f(x_2)を満たすものが存在します。

証明.ffが単射であると仮定します。このとき、各x∈Xx\in Xは互いに異なるYYの要素へ対応するので、YYは少なくとも∣X∣|X|個の要素をもたなければなりません。これは∣X∣>∣Y∣|X|>|Y|に反します。したがってffは単射ではありません。▨

一つの箱に入る対象の個数についても下界を得ることができます。

定理 1.3 (鳩の巣原理の一般形).X,YX,Yを有限集合とし、rrを正の整数とします。∣X∣>r∣Y∣|X|>r|Y|ならば、あるy∈Yy\in Yが存在して∣f−1({y})∣≥r+1|f^{-1}(\{y\})|\ge r+1が成り立ちます。

証明. すべての箱に高々rr個しか入らないと仮定すると、対象の総数は高々r∣Y∣r|Y|個です。これは∣X∣>r∣Y∣|X|>r|Y|に反します。▨

2 同じ要素数の有限集合

要素数の等しい有限集合の間の写像については、単射であることと全射であることの一方だけを確かめれば、もう一方も従います。

定理 2.1.X,YX,Yを∣X∣=∣Y∣|X|=|Y|を満たす有限集合とし、f:X→Yf:X\to Yを写像とします。次は同値です。

  1. ffは単射です。
  2. ffは全射です。
  3. ffは全単射です。

証明.ffが単射ならば、∣X∣|X|個の異なる像があります。∣X∣=∣Y∣|X|=|Y|なので像はYY全体であり、ffは全射です。逆に、ffが全射で単射でないと仮定すると、二つ以上の要素が入る箱が存在します。全射なので空の箱はなく、∣X∣|X|個の対象だけでは∣Y∣=∣X∣|Y|=|X|個の箱をすべて埋めることができません。これは全射性に反します。したがってffは単射です。▨

例 2.2. 整数を13個選びます。12で割った余りは0から11までの12種類なので、鳩の巣原理により同じ余りをもつ2個が存在します。その差は12の倍数です。

例 2.3. うるう日を除く365日だけを誕生日の候補とします。366人を誕生日によって分類すると、同じ誕生日の2人が存在します。この結論は誕生日の分布が一様であることを仮定しません。

何を対象とし、何を箱とみなすかを設計する競技数学での使い方は、§C5.1 鳩の巣原理の応用で扱います。

3 演習

問題 3.1. 1以上10以下の整数から相異なる6個を選ぶと、差が5の倍数である2個が存在することを証明せよ。

解答.

選んだ6個の整数の集合をXXとし、5で割った余り0,1,2,3,40,1,2,3,4の集合をYYとする。各整数に5で割った余りを対応させる写像をf:X→Yf:X\to Yとする。∣X∣=6>5=∣Y∣|X|=6>5=|Y|なので、定理 1.2により、異なるx1,x2∈Xx_1,x_2\in Xでf(x1)=f(x2)f(x_1)=f(x_2)を満たすものが存在する。x1x_1とx2x_2は5で割った余りが等しいので、差x1−x2x_1-x_2は5の倍数である。▨

問題 3.2.X,YX,Yが同じ要素数をもつ有限集合で、f:X→Yf:X\to Yが全射であるとき、ffが単射であることを、空の箱と二個以上の対象が入る箱の個数に着目して証明せよ。

解答.

ffが単射でないと仮定する。このとき、異なるx1,x2∈Xx_1,x_2\in Xでf(x1)=f(x2)f(x_1)=f(x_2)を満たすものが存在する。y0=f(x1)y_0=f(x_1)とすると、箱y0y_0には二個以上の対象が入り、∣f−1({y0})∣≥2|f^{-1}(\{y_0\})|\ge2である。ffは全射なので空の箱はなく、すべてのy∈Yy\in Yについて∣f−1({y})∣≥1|f^{-1}(\{y\})|\ge1である。各対象はちょうど一つの箱に入るので、

∣X∣=∑y∈Y∣f−1({y})∣≥2+(∣Y∣−1)=∣Y∣+1|X|=\sum_{y\in Y}|f^{-1}(\{y\})|\ge2+(|Y|-1)=|Y|+1

である。したがって∣X∣>∣Y∣|X|>|Y|であり、∣X∣=∣Y∣|X|=|Y|と両立しない。よって、ffは単射である。▨

問題 3.3. 25個の対象を6個の箱へ入れるとき、少なくとも一つの箱に5個以上の対象が入ることを、定理 1.3から示せ。

解答.

対象の集合をXX、箱の集合をYYとし、各対象にそれが入る箱を対応させる写像をf:X→Yf:X\to Yとする。∣X∣=25|X|=25、∣Y∣=6|Y|=6であり、25>24=4⋅625>24=4\cdot6なので∣X∣>4∣Y∣|X|>4|Y|である。定理 1.3をr=4r=4として適用すると、あるy∈Yy\in Yが存在して∣f−1({y})∣≥5|f^{-1}(\{y\})|\ge5が成り立つ。したがって、箱yyには5個以上の対象が入る。▨

問題 3.4.例 2.2で、13個の整数から12で割った余りが等しい2個が存在することは保証されるが、その2個を数値として特定することはできない。その理由を説明せよ。

解答.

定理 1.2を適用するときに用いた情報は、対象が13個あり、余りの種類が12個あることだけであり、個々の整数の値を含まない。定理 1.2が結論するのは、同じ余りをもつ2個が存在することだけである。どの2個がそうなるかは、選んだ13個の整数の値によって変わる。たとえば0,1,…,11,120,1,\ldots,11,12の13個では同じ余りをもつ2個は00と1212だけであり、0,1,…,11,130,1,\ldots,11,13の13個では11と1313だけである。したがって、整数の値を用いずに2個を数値として特定することはできない。▨

前提記事