§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人が存在します。この結論は誕生日の分布が一様であることを仮定しません。

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

3 演習

  1. 1以上10以下の整数から6個を選ぶと、差が5の倍数である2個が存在することを証明します。
  2. X,YX,Yが同じ要素数をもつ有限集合で、f:X→Yf:X\to Yが全射であるとき、ffが単射であることを、空の箱と二個以上入る箱の個数に着目して証明します。
  3. 25個の対象を6個の箱へ入れるとき、少なくとも一つの箱に5個以上の対象が入ることを一般形から示します。
  4. 13個の整数から同じ余りをもつ2個の存在は保証されますが、その2個を数値として特定することはできない理由を説明します。

1では、5で割った余りを箱とします。6個の整数を5個の箱へ入れるので、同じ余りをもつ2個が存在します。2では、単射でなければ二個以上入る箱があり、対象と箱が同数なので空の箱が生じます。これは全射性に反します。3では25>4⋅625>4\cdot6なので、r=4r=4とした一般形を適用します。4では、原理に与えた情報が個々の整数の値を含まず、余りの種類と対象数だけだからです。

前提記事