The pigeonhole principle: a surprisingly powerful tool for existence proofs

If you place more pigeons than there are holes, some hole must contain at least two pigeons. This triviality is the starting point for the Erdos--Szekeres theorem on monotone subsequences and for Ramsey theory, illustrating the remarkable reach of non-constructive existence arguments.

Folio Official

March 1, 2026

Proving that something exists is often harder – or easier – than producing an explicit example. The pigeonhole principle provides existence proofs of a distinctive kind: it guarantees that a certain configuration must occur without identifying which one. The principle itself is almost embarrassingly simple, yet its consequences reach deep into combinatorics.

1 The basic form

Theorem 1 (Pigeonhole principle).

n + 1

or more pigeons are placed into

n

holes, then at least one hole contains two or more pigeons.

Proof.

By contraposition. If every hole contained at most one pigeon, the total number of pigeons would be at most

n

, contradicting the assumption that there are at least

n + 1

. □

Remark 2.

In mathematical language: if

∣ A ∣ > ∣ B ∣

, then no function

f : A \to B

can be injective. No matter how cleverly you assign pigeons to holes, a collision is unavoidable.

2 The generalized form

Theorem 3 (Generalized pigeonhole principle).

n

objects are distributed among

k

boxes, then at least one box contains

⌈ n / k ⌉

or more objects.

Proof.

If every box contained fewer than

⌈ n / k ⌉

objects, the total would be at most

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

, a contradiction. □

3 Simple but non-trivial applications

Example 4 (The birthday preamble).

In any group of 367 people, at least two share a birthday (accounting for leap years, there are at most 366 possible birthdays). The pigeonhole principle guarantees the existence of such a pair, even though it does not identify who they are.

Example 5 (Divisibility among chosen numbers).

Choose

n + 1

numbers from

{1, 2, \dots, 2 n}

. Then among the chosen numbers there must exist a pair in which one divides the other.

Write each integer

m

m = 2^{a} q

where

q

is odd. The odd part

q

takes values in

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

, a set of size

n

. Since we have chosen

n + 1

numbers, the pigeonhole principle guarantees two of them – say

2^{a} q

and

2^{b} q

with

a < b

– share the same odd part

q

. Then

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

4 The Erdos–Szekeres theorem

A beautiful and deeper application of the pigeonhole principle concerns monotone subsequences.

Theorem 6 (Erdos–Szekeres theorem).

Every sequence of length at least

rs + 1

contains either an increasing subsequence of length

r + 1

or a decreasing subsequence of length

s + 1

Proof.

Let the sequence be

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

. For each

a_{i}

, let

ℓ_{i}

denote the length of the longest increasing subsequence starting at

a_{i}

ℓ_{i} \geq r + 1

for some

i

, the theorem holds immediately.

Otherwise

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

for all

i

. Since

rs + 1

values are drawn from

r

possible values, the generalized pigeonhole principle guarantees at least

s + 1

indices

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

with

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

Now suppose

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

for some

j

. Then the longest increasing subsequence starting at

a_{i_{j}}

could be extended by prepending

a_{i_{j}}

to one starting at

a_{i_{j + 1}}

, giving

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

– contradicting

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

. Therefore

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

, producing a decreasing subsequence of length

s + 1

. □

Remark 7.

Setting

r = s = n

yields a particularly elegant corollary: every sequence of length

n^{2} + 1

contains a monotone subsequence of length

n + 1

. This result provides the theoretical underpinning for longest increasing subsequence (LIS) problems that frequently appear in competitive programming.

5 An introduction to Ramsey theory

Pushing the pigeonhole principle further leads to Ramsey theory.

Theorem 8 (The Ramsey number

R (3, 3) = 6

Among any six people, no matter how "friend" and "stranger" relationships are assigned, there must exist either three mutual friends or three mutual strangers.

Proof.

Pick one person

A

. Of the five remaining people,

A

is either a friend or a stranger to each. By the pigeonhole principle, at least three of them share the same relationship to

A

Suppose

A

is friends with

B

C

D

. Now examine the relationships among

B

C

D

If any two of $B$ , $C$ , $D$ are friends, those two together with $A$ form a trio of mutual friends.
If $B$ , $C$ , $D$ are all strangers to one another, they form a trio of mutual strangers.

In either case the conclusion holds. (The argument when

A

has three strangers is symmetric.) □

Remark 9.

To establish

R (3, 3) = 6

, one must also show that five people do not suffice – that is, one must construct a counterexample. Place five people at the vertices of a regular pentagon; declare adjacent vertices friends and non-adjacent vertices strangers. One can verify that no monochromatic triangle exists.

6 Existence proofs versus constructive proofs

Remark 10.

A distinguishing feature of the pigeonhole principle is its non-constructive character. It asserts "at least one hole contains two or more pigeons" but does not say which hole. This non-constructivity pervades Ramsey theory: existence is guaranteed, but a recipe for finding the guaranteed object is not provided.

From a constructivist standpoint, this may seem unsatisfying. Yet the mere guarantee of existence is often powerful information – it can settle conjectures, establish lower bounds, and rule out impossible configurations even when no explicit witness is at hand.

7 Takeaway

The pigeonhole principle states that placing $n + 1$ objects into $n$ boxes forces at least one box to contain two or more objects.
The generalized form – at least $⌈ n / k ⌉$ objects in some box – is equally useful.
The Erdos–Szekeres theorem on monotone subsequences is a striking application.
Ramsey theory is the ultimate extension: $R (3, 3) = 6$ is the gateway.
The pigeonhole principle exemplifies non-constructive existence proofs.

In the next article, we discover how symmetry can dramatically simplify counting problems, via Burnside's lemma and Polya's enumeration theorem.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The pigeonhole principle: a surprisingly powerful tool for existence proofs

Folio Official

March 1, 2026

1 The basic form

Theorem 1 (Pigeonhole principle).

n + 1

or more pigeons are placed into

n

holes, then at least one hole contains two or more pigeons.

Proof.

By contraposition. If every hole contained at most one pigeon, the total number of pigeons would be at most

n

, contradicting the assumption that there are at least

n + 1

. □

Remark 2.

In mathematical language: if

∣ A ∣ > ∣ B ∣

, then no function

f : A \to B

can be injective. No matter how cleverly you assign pigeons to holes, a collision is unavoidable.

2 The generalized form

Theorem 3 (Generalized pigeonhole principle).

n

objects are distributed among

k

boxes, then at least one box contains

⌈ n / k ⌉

or more objects.

Proof.

If every box contained fewer than

⌈ n / k ⌉

objects, the total would be at most

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

, a contradiction. □

3 Simple but non-trivial applications

Example 4 (The birthday preamble).

Example 5 (Divisibility among chosen numbers).

Choose

n + 1

numbers from

{1, 2, \dots, 2 n}

. Then among the chosen numbers there must exist a pair in which one divides the other.

Write each integer

m

m = 2^{a} q

where

q

is odd. The odd part

q

takes values in

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

, a set of size

n

. Since we have chosen

n + 1

numbers, the pigeonhole principle guarantees two of them – say

2^{a} q

and

2^{b} q

with

a < b

– share the same odd part

q

. Then

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

4 The Erdos–Szekeres theorem

A beautiful and deeper application of the pigeonhole principle concerns monotone subsequences.

Theorem 6 (Erdos–Szekeres theorem).

Every sequence of length at least

rs + 1

contains either an increasing subsequence of length

r + 1

or a decreasing subsequence of length

s + 1

Proof.

Let the sequence be

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

. For each

a_{i}

, let

ℓ_{i}

denote the length of the longest increasing subsequence starting at

a_{i}

ℓ_{i} \geq r + 1

for some

i

, the theorem holds immediately.

Otherwise

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

for all

i

. Since

rs + 1

values are drawn from

r

possible values, the generalized pigeonhole principle guarantees at least

s + 1

indices

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

with

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

Now suppose

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

for some

j

. Then the longest increasing subsequence starting at

a_{i_{j}}

could be extended by prepending

a_{i_{j}}

to one starting at

a_{i_{j + 1}}

, giving

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

– contradicting

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

. Therefore

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

, producing a decreasing subsequence of length

s + 1

. □

Remark 7.

Setting

r = s = n

yields a particularly elegant corollary: every sequence of length

n^{2} + 1

contains a monotone subsequence of length

n + 1

. This result provides the theoretical underpinning for longest increasing subsequence (LIS) problems that frequently appear in competitive programming.

5 An introduction to Ramsey theory

Pushing the pigeonhole principle further leads to Ramsey theory.

Theorem 8 (The Ramsey number

R (3, 3) = 6

Among any six people, no matter how "friend" and "stranger" relationships are assigned, there must exist either three mutual friends or three mutual strangers.

Proof.

Pick one person

A

. Of the five remaining people,

A

is either a friend or a stranger to each. By the pigeonhole principle, at least three of them share the same relationship to

A

Suppose

A

is friends with

B

C

D

. Now examine the relationships among

B

C

D

If any two of $B$ , $C$ , $D$ are friends, those two together with $A$ form a trio of mutual friends.
If $B$ , $C$ , $D$ are all strangers to one another, they form a trio of mutual strangers.

In either case the conclusion holds. (The argument when

A

has three strangers is symmetric.) □

Remark 9.

To establish

R (3, 3) = 6

6 Existence proofs versus constructive proofs

Remark 10.

7 Takeaway

The pigeonhole principle states that placing $n + 1$ objects into $n$ boxes forces at least one box to contain two or more objects.
The generalized form – at least $⌈ n / k ⌉$ objects in some box – is equally useful.
The Erdos–Szekeres theorem on monotone subsequences is a striking application.
Ramsey theory is the ultimate extension: $R (3, 3) = 6$ is the gateway.
The pigeonhole principle exemplifies non-constructive existence proofs.

In the next article, we discover how symmetry can dramatically simplify counting problems, via Burnside's lemma and Polya's enumeration theorem.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The pigeonhole principle: a surprisingly powerful tool for existence proofs

1 The basic form

2 The generalized form

3 Simple but non-trivial applications

4 The Erdos–Szekeres theorem

5 An introduction to Ramsey theory

6 Existence proofs versus constructive proofs

7 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

The pigeonhole principle: a surprisingly powerful tool for existence proofs

1 The basic form

2 The generalized form

3 Simple but non-trivial applications

4 The Erdos–Szekeres theorem

5 An introduction to Ramsey theory

6 Existence proofs versus constructive proofs

7 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem