鳩の巣原理 ― 「存在」を証明する意外な武器

鳩の巣原理は「引き出しに物を入れれば，どこかの引き出しには2つ以上入る」という単純な主張ですが，Erdos-Szekeres の定理やラムゼー理論の入口を開く強力な存在証明の道具です．

2026年2月27日

数学において「…が存在する」ことを証明するのは，「…を具体的に構成する」ことよりもしばしば難しい（あるいは易しい）ものです．鳩の巣原理（pigeonhole principle）は，「具体的にどこにあるかは言えないが，必ずどこかにある」という存在証明を与える，驚くほど単純で強力な原理です．

1 鳩の巣原理の基本形

定理 1 (鳩の巣原理).

n + 1

羽以上の鳩を

n

個の巣箱に入れると，少なくとも1つの巣箱には2羽以上の鳩が入ります．

証明.

対偶を示します．すべての巣箱に高々1羽しかいなければ，鳩の総数は高々

n

羽です．これは

n + 1

羽以上いるという仮定に矛盾します． □

注意 2.

数学的に言えば，

∣ A ∣ > ∣ B ∣

のとき

f : A \to B

なる関数は単射にはなれない，ということです．どんなに巧妙に割り当てても，衝突（同じ巣箱に2羽以上）は避けられません．

2 一般化鳩の巣原理

定理 3 (一般化鳩の巣原理).

n

個の物を

k

個の箱に入れると，少なくとも1つの箱には

⌈ n / k ⌉

個以上の物が入ります．

証明.

すべての箱に

⌈ n / k ⌉ - 1

個以下しかなければ，物の総数は高々

k (⌈ n / k ⌉ - 1) < k \cdot (n / k) = n

で矛盾します． □

3 具体例 ― 単純だが非自明な応用

例 4 (誕生日問題の前段).

367人の集団には，同じ誕生日の人が必ず2人以上います（うるう年考慮で366日 + 1人）．これは鳩の巣原理の直接適用です．「誰と誰が同じ誕生日か」は特定できませんが，存在は保証されます．

例 5 (部分集合の和).

{1, 2, \dots, 2 n}

から

n + 1

個の数を選ぶと，選んだ数の中に一方が他方の約数であるペアが必ず存在します．

各整数

m

を

m = 2^{a} \cdot q

（

q

は奇数）と書くと，奇数部分

q

は

{1, 3, 5, \dots, 2 n - 1}

の

n

個の値をとります．

n + 1

個の数を選ぶと，鳩の巣原理より同じ奇数部分

q

をもつ2数

2^{a} q

と

2^{b} q

（

a < b

）が存在し，

2^{a} q ∣ 2^{b} q

です．

4 Erdos-Szekeres の定理

鳩の巣原理の驚くべき応用として，単調部分列に関する美しい定理があります．

定理 6 (Erdos-Szekeres の定理).

長さ

rs + 1

以上の数列には，長さ

r + 1

以上の単調増加部分列か，長さ

s + 1

以上の単調減少部分列が必ず存在します．

証明.

数列を

a_{1}, a_{2}, \dots, a_{rs + 1}

とします．各

a_{i}

に対して，

a_{i}

から始まる最長単調増加部分列の長さ

ℓ_{i}

を定めます．

もしある

i

で

ℓ_{i} \geq r + 1

なら定理は成立します．

そうでなければ

ℓ_{i} \in {1, 2, \dots, r}

です．

rs + 1

個の値

ℓ_{i}

が

r

種類しかないので，一般化鳩の巣原理より，同じ値をとるものが少なくとも

s + 1

個あります：

ℓ_{i_{1}} = ℓ_{i_{2}} = \dots = ℓ_{i_{s + 1}}

（

i_{1} < i_{2} < \dots < i_{s + 1}

）．

ここで

a_{i_{j}} \leq a_{i_{j + 1}}

だとすると，

a_{i_{j}}

から始まる最長増加部分列に

a_{i_{j + 1}}

を先頭に追加できて

ℓ_{i_{j}} > ℓ_{i_{j + 1}}

となり

ℓ_{i_{j}} = ℓ_{i_{j + 1}}

に矛盾します．よって

a_{i_{1}} > a_{i_{2}} > \dots > a_{i_{s + 1}}

で，長さ

s + 1

の単調減少部分列が得られます． □

注意 7.

r = s = n

とすると，「長さ

n^{2} + 1

以上の数列には長さ

n + 1

の単調部分列が存在する」という美しい系が得られます．これは AtCoder でも最長増加部分列（LIS）の問題の理論的背景になっています．

5 ラムゼー理論への導入

鳩の巣原理を押し進めるとラムゼー理論に到達します．

定理 8 (ラムゼー数

R (3, 3) = 6

6人の集団において，どのように「友人」「他人」の関係を定めても，3人の「全員が友人同士」か3人の「全員が他人同士」が必ず存在します．

証明.

6人のうち1人を

A

とします．

A

と残り5人の関係を「友人」「他人」に分類すると，鳩の巣原理より少なくとも3人は同じ関係です．

A

と友人であるような3人を

B, C, D

としましょう．

B, C, D

の間の関係を考えます：

$B, C, D$ のうちどれか2人が友人であれば，その2人と $A$ で「全員友人」の3人組ができます
$B, C, D$ が全員他人同士であれば，「全員他人」の3人組ができます

どちらの場合も条件を満たします（

A

が他人3人を持つ場合も対称的に同様）． □

注意 9.

R (3, 3) = 6

は「5人では足りない」ことの証明も必要です（反例の構成）．5人を正五角形の頂点に配置し，隣り合う人を友人，対角の人を他人とすると，全員友人の3人組も全員他人の3人組も存在しません．

6 存在証明 vs 構成的証明

注意 10.

鳩の巣原理の特徴は非構成的であることです．「少なくとも1つの巣箱に2羽以上いる」とは言えますが，「どの巣箱か」は特定しません．この非構成性はラムゼー理論に共通する特徴であり，「存在は保証するが見つけ方は教えてくれない」という独特の性格をもっています．

構成的証明を求める立場からは物足りないかもしれませんが，存在を保証すること自体が強力な情報になることは多くあります．

7 まとめ

鳩の巣原理は「 $n + 1$ 個を $n$ 箱に入れればどこかに2個以上」という単純な原理です
一般化形「 $⌈ n / k ⌉$ 個以上」も頻繁に使います
Erdos-Szekeres の定理は鳩の巣原理の美しい応用です
ラムゼー理論は鳩の巣原理の究極の拡張で， $R (3, 3) = 6$ はその入口です
鳩の巣原理は非構成的な存在証明の典型例です

次の記事では，対称性を使って数え上げを劇的に簡単にする ― バーンサイドの補題とポリアの数え上げ定理を紹介します．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

鳩の巣原理 ― 「存在」を証明する意外な武器

1 鳩の巣原理の基本形

2 一般化鳩の巣原理

3 具体例 ― 単純だが非自明な応用

4 Erdos-Szekeres の定理

5 ラムゼー理論への導入

6 存在証明 vs 構成的証明

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ