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
If n+1 or more pigeons are placed into n holes, then at least one hole contains two or more pigeons.
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. □
2 The generalized form
If n objects are distributed among k boxes, then at least one box contains ⌈n/k⌉ or more objects.
If every box contained fewer than ⌈n/k⌉ objects, the total would be at most k(⌈n/k⌉−1)<k⋅(n/k)=n, a contradiction. □
3 Simple but non-trivial applications
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.
Choose n+1 numbers from {1,2,…,2n}. Then among the chosen numbers there must exist a pair in which one divides the other.Write each integer m as m=2aq where q is odd. The odd part q takes values in {1,3,5,…,2n−1}, a set of size n. Since we have chosen n+1 numbers, the pigeonhole principle guarantees two of them – say 2aq and 2bq with a<b– share the same odd part q. Then 2aq∣2bq.
4 The Erdos–Szekeres theorem
A beautiful and deeper application of the pigeonhole principle concerns monotone subsequences.
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.
Let the sequence be a1,a2,…,ars+1. For each ai, let ℓi denote the length of the longest increasing subsequence starting at ai.If ℓi≥r+1 for some i, the theorem holds immediately.Otherwise ℓi∈{1,2,…,r} for all i. Since rs+1 values are drawn from r possible values, the generalized pigeonhole principle guarantees at least s+1 indices i1<i2<⋯<is+1 with ℓi1=ℓi2=⋯=ℓis+1.Now suppose aij≤aij+1 for some j. Then the longest increasing subsequence starting at aij could be extended by prepending aij to one starting at aij+1, giving ℓij>ℓij+1– contradicting ℓij=ℓij+1. Therefore ai1>ai2>⋯>ais+1, producing a decreasing subsequence of length s+1. □
5 An introduction to Ramsey theory
Pushing the pigeonhole principle further leads to Ramsey theory.
Among any six people, no matter how "friend" and "stranger" relationships are assigned, there must exist either three mutual friends or three mutual strangers.
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.) □
6 Existence proofs versus constructive proofs
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.