The Pigeonhole Principle: How a Trivial Statement Proves Non-Trivial Theorems — Epoche B2
Introduction Many students meet the pigeonhole principle at school and dismiss it as a joke: if $n+1$ objects are placed in $n$ boxes, some box contains at least two objects. The proof is one line — if every box held at most one object, the boxes could hold at most $n$ objects in total, contradicting the fact that $n+1$ were placed — and the statement seems too obvious to be useful. This essay argues the opposite. The principle is what mathematicians call non-constructive : it guarantees that something exists (a crowded box) without telling you which box it is or how to find it. Precisely because it guarantees existence without constructing anything, it proves theorems that no direct calculation could easily reach. The entire craft lies in one decision: what to count as the objects, and what to count as the boxes. Three examples of increasing depth will illustrate the point. Example 1: Hairs on London heads A human head carries fewer than $200{,}000$ hairs — anatomical estimates put the average scalp at roughly $100{,}000$ hair follicles, so $200{,}000$ is a deliberately generous ceiling — while London has more than $8$ million residents (the 2021 census counted about $8.8$ million). Treat each possible hair count $0, 1, \dots, 199{,}999$ as a box and each Londoner as an object: a person "goes into" the box labelled with their exact number of hairs. There are $2 \times 10^5$ boxes and more than $8 \times 10^6$ objects, and since $8 \times 10^6 > 2 \times 10^5$, at least two Londoners have exactly the same number of hairs. The principle also comes in a stronger, averaged form: if more than $kn$ objects go into $n$ boxes, some box holds at least $k+1$. The reasoning is the same contradiction — if every box held at most $k$, the total would be at most $kn$. Here $kn = 40 \times 200{,}000 = 8{,}000{,}000$, so with more than $8$ million residents some single hair count is shared by at least $41$ Londoners; the average box holds over $40$ people. We cannot name the pair, or the crowded hair count — and we do not need to. Existence is established without any search, and no conceivable census of hair counts could be carried out anyway. That is the non-constructive bargain: total certainty about that , total silence about which . Example 2: Monotone subsequences (Erdős–Szekeres) The second example needs two definitions. A subsequence of a sequence is what remains after deleting some terms without reordering the rest — the terms kept need not be adjacent, so $2, 5, 9$ is a subsequence of $2, 7, 5, 1, 9$. A subsequence is monotone if it runs entirely upwards or entirely downwards. In 1935, Erdős and Szekeres proved that any sequence of $n^2+1$ distinct real numbers contains a monotone subsequence of length $n+1$. So among any $10$ distinct numbers ($n = 3$: $3^2 + 1 = 10$) there is always a rising or falling run of $4$, however adversarially the numbers are arranged. Their original 1935 argument was a different, inductive one; the elegant pigeonhole proof presented here is due to Seidenberg (1959). Assign to each term $a_i$ a pair of labels $(x_i, y_i)$: $x_i$ is the length of the longest increasing subsequence that ends at $a_i$, and $y_i$ the length of the longest decreasing one ending there. The key observation is that no two terms can share the same pair. Take $a_i$ before $a_j$ in the sequence. Since all terms are distinct, either $a_i a_j$. If $a_i a_j$, the same appending argument on the decreasing side gives $y_j \ge y_i + 1$. Either way, one coordinate is forced to grow, so all $n^2 + 1$ pairs are distinct. Now count the boxes. Suppose, aiming at a contradiction, that no monotone subsequence has length $n+1$; then every $x_i$ and every $y_i$ lies between $1$ and $n$, so there are at most $n \times n = n^2$ possible pairs — the boxes — but $n^2 + 1$ terms — the objects. The pigeonhole principle forces two terms into one box, i.e. two equal pairs, which we have just shown impossible. Hence some $x_i$ or some $y_i$ reaches $n+1$: a monotone subsequence of the promised length exists. The bound is sharp, meaning the theorem fails if $n^2+1$ is weakened to $n^2$, and one bad sequence proves it. Arrange $n^2$ numbers in $n$ blocks of $n$, the numbers falling within each block but every number of a block lying below every number of the block that follows. Concretely, for $n = 3$: $$3,\,2,\,1,\;\;6,\,5,\,4,\;\;9,\,8,\,7.$$ An increasing subsequence can use at most one number from each block (within a block the numbers fall), so its length is at most $3$; a decreasing subsequence must stay inside a single block (each later block starts above where the previous one ended, so crossing blocks forces a rise), so its length is also at most $3$. Length $n^2$ admits no monotone run of $n+1$; one extra term makes it unavoidable. Example 3: Dirichlet's approximation theorem Dirichlet applied the same idea to number theory, to the question of how well an irrational number — one that is not a ratio of integers, like $\sqrt2$ or $\pi$ — can be approximated by fractions. A benchmark first: truncating a decimal expansion after $k$ digits approximates $\alpha$ with denominator $q = 10^k$ and error up to $1/q$ in order of magnitude. Dirichlet's theorem guarantees something far better: fractions $p/q$ whose error is smaller than $1/q^2$ — the approximation is good not merely in proportion to the denominator, but to its square. The proof is pigeonholes again, with boxes cut out of the unit interval. Write $\{t\}$ for the fractional part of $t$, the part after the decimal point, so $\{3.71\} = 0.71$; every fractional part lies in $[0,1)$. Divide $[0,1)$ into $N$ equal boxes $[0, \tfrac1N), [\tfrac1N, \tfrac2N), \dots$ and consider the $N+1$ numbers $\{0\cdot\alpha\}, \{1\cdot\alpha\}, \{2\cdot\alpha\}, \dots, \{N\alpha\}$ for an irrational $\alpha$. There are $N+1$ objects and $N$ boxes, so two of them, say $\{i\alpha\}$ and $\{j\alpha\}$ with $i $$\left| \alpha - \frac{p}{q} \right| where the last step uses $q \le N$