鳩の巣原理

同義語：pigeonhole principle部屋割り論法引き出し論法Dirichlet's box principle

概要

定義

$n+1$ 羽の鳩が $n$ 個の巣に入れば、2 羽以上が入っている巣が少なくとも 1 つある。鳩の巣原理はこの当たり前の観察を、有限集合の間の写像についての命題として述べたものである。鳩を集合 $A$ の元、巣を集合 $B$ の元とし、各鳩がどの巣に入るかを写像 $f\colon A\to B$ で表す。巣 $b\in B$ に入っている鳩の全体は逆像 $f^{-1}(b):=\{a\in A\mid f(a)=b\}$ である。以下、有限集合 $X$ の元の個数を $|X|$ と書く。

鳩の巣原理の基本形

$A,B$ を有限集合とし、$|A|>|B|$ とする。このとき任意の写像 $f\colon A\to B$ は単射でない。すなわち $a\neq a'$ かつ $f(a)=f(a')$ となる $a,a'\in A$ が存在する。言い換えると、ある $b\in B$ について $|f^{-1}(b)|\ge2$ である。

$n:=|B|$ に関する数学的帰納法で示す。$n=0$ のとき $B=\emptyset$ で、$|A|>0$ より $A$ は空でないので、$A$ から $B$ への写像はそもそも存在せず、主張は自明に成り立つ。
$n\ge0$ とし、元の個数が $n$ の集合 $B$ については主張が成り立つとする。$|B|=n+1$、$|A|>n+1$ とし、$f\colon A\to B$ が単射であると仮定して矛盾を導く。$b\in B$ を 1 つとる。$f$ は単射なので $f^{-1}(b)$ は高々 1 個の元しか含まない。$A':=A\setminus f^{-1}(b)$、$B':=B\setminus\{b\}$ とおくと、$A'$ の元の像は $b$ でないので、$f$ は写像 $f'\colon A'\to B'$ を定め、$f'$ も単射である。一方
$$ |A'|=|A|-|f^{-1}(b)|\ge|A|-1>n=|B'| $$
であるから、帰納法の仮定により $f'$ は単射でない。これは矛盾である。よって $f$ は単射でない。$\square$

対偶をとると、有限集合 $A,B$ の間に単射 $A\to B$ があれば $|A|\le|B|$ である。定理を $|B|=n\ge1$ の場合に読めば、「$n+1$ 個以上の物を $n$ 個の箱に入れると、2 個以上入った箱がある」という日常の言い方になる。この原理は Dirichlet の箱入れ原理（Dirichlet's box principle）とも呼ばれ、日本語では 部屋割り論法・引き出し論法 ともいう。
鳩の巣原理は、どの巣に 2 羽いるかを教えない。存在だけを保証し、しかもその証明は「数が合わない」ことだけによる。応用では、何を鳩とし何を巣とするかを決めることが議論の中心になる。

同じ個数の有限集合の間の写像

$A,B$ を有限集合とし、$|A|=|B|$ とする。写像 $f\colon A\to B$ について、次の 3 条件は同値である。

$f$ は単射である。
$f$ は全射である。
$f$ は全単射である。

3 から 1 と 2 は定義から従う。1 と 2 がともに 3 を導くことを示せばよい。
1 ⇒ 2：$f$ が単射で全射でないとし、$b\in B$ が像に属さないとする。すると $f$ は単射 $A\to B\setminus\{b\}$ を定めるが、$|A|=|B|>|B\setminus\{b\}|$ なので thm-pigeonhole-basic に反する。よって $f$ は全射であり、全単射である。
2 ⇒ 1：$f$ が全射なら、各 $b\in B$ について $f^{-1}(b)$ は空でないので、その元 $s(b)$ を 1 つずつ選べる（$B$ は有限なので選択公理は要らない）。$f(s(b))=b$ であるから $s\colon B\to A$ は単射であり、$|B|=|A|$ なので 1 ⇒ 2 により $s$ は全単射である。$f\circ s=\mathrm{id}_B$ の右から $s^{-1}$ を合成すると $f=s^{-1}$ となり、$f$ は全単射である。$\square$

直感

鳩の巣原理は「足りない」ことを利用する論法である。巣が $n$ 個しかないのに鳩が $n+1$ 羽いれば、全員に別々の巣を割り当てることはできない。応用の多くは次の形をとる。示したい構造が存在しないと仮定し、各対象にその「状態」（余り、区間、長さの組など）を割り当てる。状態の個数が対象の個数より少なければ、同じ状態をもつ 2 つの対象があり、その 2 つを比べると示したい構造が現れる。鳩と巣の設計が適切なら、この論法は構成的な方法では見つけにくい存在定理を数行で与える。

例と反例

誕生日と生まれ月

13 人いれば、同じ月に生まれた 2 人がいる。人の集合 $A$ から 12 か月の集合 $B$ への「生まれ月」の写像に thm-pigeonhole-basic を使えばよい。同様に 367 人いれば、2 月 29 日を含めた 366 通りの誕生日のうち同じ日の 2 人がいる。どの 2 人かは分からないが、存在は確実である。12 人では、全員の生まれ月が異なる場合がありうる。

同じ余りをもつ整数

$n\ge1$ とする。どの $n+1$ 個の整数の中にも、差が $n$ で割り切れる相異なる 2 つがある。実際、整数をその $n$ で割った余り（$0,1,\dots,n-1$ の $n$ 通り、除法の原理）に写すと、thm-pigeonhole-basic により同じ余りの 2 つ $a\neq a'$ があり、$n\mid a-a'$ である（合同式）。$n$ 個では成り立たない。$0,1,\dots,n-1$ の相異なる 2 つの差の絶対値は $1$ 以上 $n-1$ 以下で、$n$ で割り切れない。

知人の数が等しい 2 人

$n\ge2$ 人の集まりで、「知り合いである」という関係が対称であるとする。このとき、集まりの中の知人の数が等しい 2 人がいる。
各人の知人の数は $0,1,\dots,n-1$ のどれかで、$n$ 通りある。しかし知人が $0$ 人の人と $n-1$ 人の人は同時にはいない。$n-1$ 人の知人をもつ人は他の全員と知り合いなので、知人が $0$ 人の人とも知り合いになってしまうからである。したがって実際に現れる値は $\{0,1,\dots,n-2\}$ か $\{1,2,\dots,n-1\}$ のどちらかに含まれ、どちらも $n-1$ 個の値である。$n$ 人をこの $n-1$ 個の値に写せば、thm-pigeonhole-basic により値の等しい 2 人がいる。
グラフの言葉では、頂点が 2 個以上の有限単純グラフには次数(グラフ)の等しい 2 頂点がある、ということである。

反例：鳩と巣が同数

$A=B=\{1,\dots,n\}$、$f=\mathrm{id}$ とすると、どの巣にも鳩はちょうど 1 羽である。この例は「$|A|\ge|B|$ なら $f\colon A\to B$ は単射でない」という含意を破る。thm-pigeonhole-basic の仮定 $|A|>|B|$ を $|A|\ge|B|$ に弱めることはできず、「$n+1$ 羽」の $n+1$ は減らせない。

反例：無限集合では「真部分集合への単射」がありうる

自然数全体 $\mathbb{N}=\{0,1,2,\dots\}$ から $\mathbb{N}\setminus\{0\}$ への写像 $n\mapsto n+1$ は単射である。巣の集合 $\mathbb{N}\setminus\{0\}$ は鳩の集合 $\mathbb{N}$ から 1 元を除いた真部分集合なのに、どの巣にも鳩は高々 1 羽である。この例は「$B\subsetneq A$ なら単射 $A\to B$ は存在しない」という含意を破り、満たさない仮定は「$A$ が有限である」ことである。有限集合ではこの含意は thm-pigeonhole-basic から従う（$B\subsetneq A$ なら $|B|<|A|$）。無限集合についての鳩の巣原理は prop-pigeonhole-infinite で扱う。

性質

一般化された鳩の巣原理

1 つの巣に入る鳩の数を 2 羽以上ではなく $k+1$ 羽以上と数えると、次の形になる。

一般化された鳩の巣原理

$A,B$ を有限集合、$f\colon A\to B$ を写像とする。

整数 $k\ge0$ について $|A|>k|B|$ なら、ある $b\in B$ について $|f^{-1}(b)|\ge k+1$ である。
$B\neq\emptyset$ なら、ある $b\in B$ について $|f^{-1}(b)|\ge\lceil |A|/|B|\rceil$ である。ここで $\lceil x\rceil$ は実数 $x$ 以上の最小の整数である。
各 $b\in B$ に整数 $k_b\ge0$ が与えられ、$|A|>\sum_{b\in B}k_b$ なら、ある $b\in B$ について $|f^{-1}(b)|\ge k_b+1$ である。

逆像 $f^{-1}(b)$（$b\in B$）は互いに交わらず、その和集合は $A$ である。有限集合の和の法則（数え上げ組合せ論の記事の命題「和の法則と積の法則」）により
$$ |A|=\sum_{b\in B}|f^{-1}(b)| $$
である。
3：すべての $b$ で $|f^{-1}(b)|\le k_b$ なら、上の式から $|A|\le\sum_bk_b$ となり仮定に反する。
1：3 で $k_b:=k$（すべての $b$）とすればよい。
2：$m:=\lceil |A|/|B|\rceil$ とおくと、$m$ の最小性から $m-1<|A|/|B|$、すなわち $|A|>(m-1)|B|$ である。$m\ge1$ なら 1 を $k:=m-1$ に使えばよい。$m\le0$ なら $|f^{-1}(b)|\ge0\ge m$ は任意の $b$ について成り立ち、$B\neq\emptyset$ なので $b$ がとれる。$\square$

$k=1$ の 1 が thm-pigeonhole-basic である。2 の下界 $\lceil |A|/|B|\rceil$ は最良である。$|A|=q|B|+r$（$0\le r<|B|$）と割り、$r$ 個の巣に $q+1$ 羽、残りの巣に $q$ 羽を入れれば、どの巣の鳩も $\lceil |A|/|B|\rceil$ 羽以下になるからである。2 は「どこかの巣には平均以上の鳩がいる」ということでもあり、巣が互いに重なってよい形は数え上げ組合せ論の記事の定理「有限被覆の平均下界」にある。

靴下を取り出す

赤・青・緑・黒の 4 色の靴下が十分多く入った袋から、暗闇で靴下を取り出す。同じ色の靴下を確実に 6 枚得るには 21 枚取り出せばよい。21 枚を 4 色に写すと、$21>5\cdot4$ なので thm-pigeonhole-general の 1（$k=5$）により 6 枚以上ある色がある。20 枚では各色 5 枚ずつという場合があるので足りない。色ごとに必要な枚数が異なるとき、たとえば「赤を 2 枚、または他のどれかの色を 6 枚」を確実に得たいときは 3 を $k_{\text{赤}}=1$、他の色で $k_b=5$ として使う。$1+5+5+5=16$ なので 17 枚取り出せばよく、赤 1 枚と他の色 5 枚ずつの 16 枚では足りない。

整数と数列への応用

連続する項の和の整除

$n\ge1$ とし、$a_1,\dots,a_n$ を整数とする。このとき、ある $1\le i\le j\le n$ について $a_i+a_{i+1}+\cdots+a_j$ は $n$ で割り切れる。

$s_0:=0$、$s_k:=a_1+\cdots+a_k$（$1\le k\le n$）とおく。$n+1$ 個の整数 $s_0,s_1,\dots,s_n$ を $n$ で割った余りに写すと、ex-pigeonhole-residues と同じく thm-pigeonhole-basic により、ある $0\le i< j\le n$ で $s_i$ と $s_j$ の余りが等しい。このとき
$$ s_j-s_i=a_{i+1}+a_{i+2}+\cdots+a_j $$
は $n$ で割り切れる。$i+1\le j$ なので、これは求める和である。$\square$

たとえば $n=5$、列 $3,1,4,1,5$ では $s_0,\dots,s_5=0,3,4,8,9,14$、5 で割った余りは $0,3,4,3,4,4$ であり、$s_1$ と $s_3$ の余りが等しいので $a_2+a_3=1+4=5$ が 5 で割り切れる。

一方が他方を割り切る 2 数

$n\ge1$ とする。$\{1,2,\dots,2n\}$ から相異なる $n+1$ 個の整数を選ぶと、その中に一方が他方を割り切る相異なる 2 数がある。

正の整数 $m$ は $m=2^eu$（$e\ge0$、$u$ は奇数）の形にただ 1 通りに書ける（$m$ を 2 で割り切れなくなるまで割る）。この $u$ を $m$ の奇数部分と呼ぶ。$1\le m\le2n$ なら奇数部分は $1,3,\dots,2n-1$ の $n$ 通りのどれかである。選んだ $n+1$ 個を奇数部分に写すと、thm-pigeonhole-basic により奇数部分の等しい 2 数 $m=2^eu$、$m'=2^{e'}u$（$m\neq m'$）がある。$m\neq m'$ から $e\neq e'$ であり、$e< e'$ なら $m\mid m'$、$e>e'$ なら $m'\mid m$ である。$\square$

$n$ 個では成り立たない。$\{n+1,n+2,\dots,2n\}$ の相異なる 2 数 $m< m'$ については $m'<2n+2\le 2m$ なので $m'$ は $m$ の倍数でない。
次の定理は、長い数列には必ず単調な部分が現れることを述べる。数列 $a_1,\dots,a_N$ の部分列とは、添字 $i_1< i_2<\cdots< i_\ell$ を選んで得られる列 $a_{i_1},\dots,a_{i_\ell}$ のことであり、$\ell$ をその長さという。$a_{i_1}<\cdots< a_{i_\ell}$ のとき増加部分列、$a_{i_1}>\cdots>a_{i_\ell}$ のとき減少部分列という。

Erdős–Szekeres の定理

$n\ge1$ とし、$a_1,\dots,a_{n^2+1}$ を相異なる実数の列とする。このとき、長さ $n+1$ の増加部分列または長さ $n+1$ の減少部分列が存在する（ES35、Juk11 Chapter 4）。

各 $i$ について、$a_i$ で終わる増加部分列の長さの最大値を $p_i$、$a_i$ で終わる減少部分列の長さの最大値を $q_i$ とする（長さ 1 の部分列 $a_i$ があるので $p_i,q_i\ge1$）。長さ $n+1$ の増加部分列も減少部分列もないと仮定すると、$1\le p_i,q_i\le n$ であり、$i\mapsto(p_i,q_i)$ は $n^2+1$ 個の添字から $n^2$ 個の組の集合 $\{1,\dots,n\}\times\{1,\dots,n\}$ への写像になる。thm-pigeonhole-basic により、ある $i< j$ で $(p_i,q_i)=(p_j,q_j)$ である。$a_i< a_j$ なら、$a_i$ で終わる長さ $p_i$ の増加部分列の後に $a_j$ を付け加えると $a_j$ で終わる長さ $p_i+1$ の増加部分列が得られ、$p_j\ge p_i+1$ となって矛盾する。$a_i>a_j$ なら同様に $q_j\ge q_i+1$ となって矛盾する。$a_i\neq a_j$ なのでどちらかが起こり、仮定は誤りである。$\square$

反例：項数が $n^2$ の数列

thm-pigeonhole-erdos-szekeres の $n^2+1$ は $n^2$ に減らせない。$n$ 個のブロック
$$ n,n-1,\dots,1,\quad 2n,2n-1,\dots,n+1,\quad\dots,\quad n^2,n^2-1,\dots,n^2-n+1 $$
を並べた $n^2$ 項の数列を考える。各ブロックの中では値が減少し、後のブロックの値はどれも前のブロックの値より大きい。増加部分列は同じブロックから 2 項をとれないので長さは高々 $n$、減少部分列は 2 つのブロックにまたがれないので長さは高々 $n$ である。この例は「$n^2$ 項の相異なる実数の列は長さ $n+1$ の単調部分列をもつ」という含意を破る。たとえば $n=2$ では $2,1,4,3$ である。

有理数による近似

実数 $x$ の小数部分を $\{x\}:=x-\lfloor x\rfloor\in[0,1)$ と書く（$\lfloor x\rfloor$ は $x$ 以下の最大の整数、床関数）。

Dirichlet の近似定理

$\alpha$ を実数、$N\ge1$ を整数とする。このとき
$$ 1\le q\le N,\qquad |q\alpha-p|<\frac1N $$
を満たす整数 $p,q$ が存在する。とくに $\left|\alpha-\dfrac pq\right|<\dfrac1{qN}\le\dfrac1{q^2}$ である（HW08 Chapter XI）。

区間 $[0,1)$ を $N$ 個の半開区間 $I_t:=[t/N,(t+1)/N)$（$t=0,1,\dots,N-1$）に分ける。これらは互いに交わらず $[0,1)$ を覆う。$N+1$ 個の数 $\{0\cdot\alpha\},\{1\cdot\alpha\},\dots,\{N\alpha\}$ はそれぞれどれか 1 つの $I_t$ に属するので、thm-pigeonhole-basic により、ある $0\le i< j\le N$ で $\{i\alpha\}$ と $\{j\alpha\}$ が同じ $I_t$ に属する。長さ $1/N$ の半開区間の 2 点なので $|\{j\alpha\}-\{i\alpha\}|<1/N$ である。$q:=j-i$、$p:=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$ とおくと $1\le q\le N$ であり、
$$ q\alpha-p=(j\alpha-\lfloor j\alpha\rfloor)-(i\alpha-\lfloor i\alpha\rfloor)=\{j\alpha\}-\{i\alpha\} $$
なので $|q\alpha-p|<1/N$ である。両辺を $q$ で割り、$q\le N$ を使えば最後の不等式を得る。$\square$

この定理から、無理数 $\alpha$ には $|\alpha-p/q|<1/q^2$ を満たす有理数 $p/q$ が無限個あり、有理数にはそのような有理数が有限個しかないことが従う。これは無理数の特徴づけになる（無理数の記事の定理「近似による無理数の特徴づけ」）。

無限集合の場合

無限集合では、元の個数の代わりに濃度で大きさを比べる（基数）。濃度の大小 $|A|>|B|$ は、Cantor–Bernstein の定理（基数の記事の定理「Cantor–Bernstein の定理：単射の往復から全単射」）により「$B$ から $A$ への単射は存在するが、$A$ から $B$ への単射は存在しない」ことと同値である。したがって thm-pigeonhole-basic をそのまま濃度で言い換えた命題「$|A|>|B|$ なら単射 $A\to B$ は存在しない」は、濃度の大小の意味から直ちに従う。有限の場合の thm-pigeonhole-basic の内容は、数えた個数の大小が単射の有無と一致することにある。基数の記事の命題「有限基数と $\omega$」の 1（$n+1$ から $n$ への単射は存在しない）は、この事実を集合論の自然数について述べたものである。
無限集合で意味をもつのは、「巣の数が少なければ、どこかの巣に多くの鳩がいる」という thm-pigeonhole-general の側の類似である。

無限集合の鳩の巣原理

$f\colon A\to B$ を写像とする。

$A$ が無限集合で $B$ が有限集合なら、ある $b\in B$ について $f^{-1}(b)$ は無限集合である。
$A$ が非可算集合で $B$ が可算集合なら、ある $b\in B$ について $f^{-1}(b)$ は非可算である。

どちらも $A=\bigcup_{b\in B}f^{-1}(b)$ による。
1：すべての $f^{-1}(b)$ が有限なら、$A$ は有限個の有限集合の和集合であり、その元の個数は $\sum_{b\in B}|f^{-1}(b)|$ なので有限である。これは $A$ が無限であることに反する。
2：すべての $f^{-1}(b)$ が可算なら、$A$ は可算個の可算集合の和集合であり、可算集合の記事の定理「可算個の可算集合の和集合」により可算である。これは $A$ が非可算であることに反する。この定理は各 $f^{-1}(b)$ の番号付けを同時に選ぶために可算選択公理を使う。$\square$

1 から、有限集合に値をとる数列 $(x_m)_{m\in\mathbb{N}}$ は定数の部分列をもつ。$m\mapsto x_m$ に 1 を使うと、ある値 $b$ について $\{m\mid x_m=b\}$ が無限集合になり、その元を小さい順に並べた添字の部分列は定数 $b$ である。

一般の無限基数の場合と反例

選択公理を仮定すると、prop-pigeonhole-infinite は次のように一般化される。$\kappa$ を無限基数とし、$|A|=\kappa$、$|B|<\operatorname{cf}(\kappa)$ とする（$\operatorname{cf}(\kappa)$ は $\kappa$ の共終数）。このとき任意の写像 $f\colon A\to B$ について、ある $b\in B$ で $|f^{-1}(b)|=\kappa$ となる。これは「$\operatorname{cf}(\kappa)$ 個未満の、濃度が $\kappa$ 未満の集合の和集合は濃度が $\kappa$ 未満である」ことの言い換えである（Jec03 Chapter 3）。$\aleph_0$ や $\aleph_1$ のように $\operatorname{cf}(\kappa)=\kappa$ となる基数（正則基数）では、条件は $|B|<\kappa$ である。
条件 $|B|<\operatorname{cf}(\kappa)$ を $|B|<\kappa$ に弱めることはできない。$\kappa=\aleph_\omega$ とすると $\operatorname{cf}(\aleph_\omega)=\aleph_0$ であり、$A:=\omega_\omega$（濃度 $\aleph_\omega$）を $f^{-1}(0):=\omega_0$、$f^{-1}(n):=\omega_n\setminus\omega_{n-1}$（$n\ge1$）となるように $B:=\mathbb{N}$ へ写すと、$|B|=\aleph_0<\aleph_\omega$ なのに、$f^{-1}(0)$ の濃度は $\aleph_0$、$f^{-1}(n)$ の濃度は $\aleph_n$ であり、どの逆像の濃度も $\aleph_\omega$ 未満である。この例は「$|B|<|A|$ なら濃度 $|A|$ の逆像がある」という含意を破る。
有限個の色で塗り分ける対象を元から 2 元部分集合に替えると、Ramseyの定理になる。$\mathbb{N}$ の 2 元部分集合全体を有限個の色で塗ると、無限部分集合 $H\subset\mathbb{N}$ で $H$ の 2 元部分集合がすべて同じ色になるものが存在する（Jec03 Chapter 9）。1 元部分集合を塗る場合がちょうど prop-pigeonhole-infinite の 1 である。