More things than boxes

Thirteen objects, twelve boxes. Some box holds at least two.

That is the whole statement, and it is difficult to find anyone who disagrees with it. What is worth explaining is why something so obviously true is worth naming, and how a proposition nobody can doubt goes on to settle questions that resist every other approach.

Why the picture is drawn that way #

The figure could have piled everything into one box and made the point trivially. It does the opposite: it spreads the items as evenly as the boxes allow, and shows that even that arrangement overflows.

That is the argument’s actual shape. The claim is not about a particular distribution — it is about all of them at once, and the way to establish something about all of them is to identify the one that comes closest to escaping and show that it fails too. With thirteen into twelve, the best possible attempt puts one item in each of twelve boxes and has one left over with nowhere to go.

Generalised: $n$ items in $k$ boxes forces some box to hold at least $\lceil n/k \rceil$. The most even split gives each box $\lfloor n/k \rfloor$ and distributes the remainder one apiece, so the fullest box is exactly the ceiling — and no arrangement does better, because doing better would mean every box holding fewer, which would account for fewer than $n$ items.

That last clause is the whole proof, and it is a counting argument: assume every box holds at most $\lceil n/k\rceil - 1$, multiply by $k$, and get a total smaller than $n$. Contradiction. The generator performs the same check before drawing — it builds the most even distribution it can and requires the fullest box to hit the ceiling exactly.

What it costs and what it buys #

The principle proves that something exists without producing it, and that trade is the reason it is powerful and the reason it is sometimes unsatisfying.

Take the classic: among any group of people, two have the same number of friends within the group. With $n$ people, each has between $0$ and $n-1$ friends — that is $n$ possible values for $n$ people, which is not yet a contradiction. The extra observation is that $0$ and $n-1$ cannot both occur: if someone knows nobody, nobody knows everybody. So only $n-1$ values are actually available for $n$ people, and two must share.

The argument is airtight and it does not tell anyone which two. It gives no procedure, no candidate, no way to shorten the search. It converts a question of existence into a matter of arithmetic and abandons the constructive question entirely.

That is the standing character of these proofs. A pigeonhole argument answers is there one? with certainty and which one? with nothing at all — the same division that separates proving no route across Königsberg exists from searching for one and failing.

The non-constructive character is not a defect to be apologised for, and it is worth separating from a superficially similar situation. Euclid’s algorithm run on an irrational ratio also proves something negative — that a common measure does not exist — but it does so by exhibiting a process and showing it never halts. A pigeonhole proof exhibits nothing at all. The two are different species of argument, and the second is the cheaper: it needs only that the possibilities can be counted, which is often the one thing available about a situation nobody understands.

The one everybody knows, and what it actually says #

Two people in London have exactly the same number of hairs on their heads.

The argument: a human head carries at most about $150{,}000$ hairs, and London holds some millions of people. Millions of items, $150{,}001$ possible values, so a great many people share a count — in fact, by the ceiling bound, some hair-count is shared by at least seven people.

What makes this a good example is not the conclusion, which nobody needed. It is that the conclusion is reached without measuring anything. No head was counted. No survey was run. The claim is about a specific empirical fact concerning real people, and it is established by two rough upper bounds and a division.

That is worth pausing on, because it inverts the usual relationship between evidence and conclusion. The statement is stronger than any feasible measurement could establish — counting every Londoner’s hairs is not going to happen — and it is more certain than a measurement would be, since a survey could be miscounted and this cannot.

Where it gets sharp #

So far the applications have been recreational. The principle earns its place because of results like the next two, where nothing else works.

Rational approximation. Dirichlet used it in 1842 to prove that for any irrational $\alpha$ and any $N$, some fraction $p/q$ with $q \le N$ satisfies

$$\left|\alpha - \frac{p}{q}\right| < \frac{1}{qN}.$$

The proof drops the fractional parts of $\alpha, 2\alpha, \ldots, N\alpha$ into $N$ boxes of width $1/N$ inside the unit interval. That is $N+1$ numbers — counting $0$ — into $N$ boxes, so two land in the same box, and their difference gives the fraction. It is one paragraph, and it establishes that every irrational is approximable to within $1/q^2$ by infinitely many fractions.

That is a real theorem about the real numbers, produced by putting things in boxes. It is also the theorem the golden ratio sits at the boundary of: the constant in the bound can be improved to $1/(\sqrt5 q^2)$ and no further, and $\varphi$ is the number that stops it.

Repeating decimals. Divide any whole number by $7$ and the decimal repeats with period at most $6$. Why at most $6$? Because long division has only $7$ possible remainders, one of which is $0$, so within seven steps a remainder must recur — and once a remainder recurs the whole process repeats, since the remainder is the entire state. The principle bounds the period of every fraction: $p/q$ repeats with period less than $q$, always, with no exceptions and no computation.

That second one is the more instructive. It is not merely that a repeat happens; it is that the pigeonhole identifies the right thing to count. The remainders are the state, the state determines the future, and there are finitely many — so recurrence is forced. The same three-step argument proves that every eventually-periodic process on a finite state space is periodic, which covers a great deal of ground.

Choosing the boxes is the whole job #

Every application above turns on a decision that the principle itself does not make: what the boxes are. Once that is settled the argument is one line, and settling it is where the thinking happens.

For repeating decimals the boxes are the possible remainders. For Dirichlet’s theorem they are intervals of width $1/N$. For the hair-count claim they are possible hair counts. In each case the items are obvious and the boxes are not, and a different choice of box gives either a triviality or nothing at all.

A worked instance makes the point. Take any five points inside a unit square and claim that two of them are within $\tfrac{1}{\sqrt2}$ of each other. The items are the five points; the boxes have to be regions, and the right choice is the four quarter-squares. Five points into four quarters forces two into one quarter, and a quarter-square of side $\tfrac12$ has diagonal $\tfrac{1}{\sqrt2}$ — so the two are at most that far apart.

Nothing in the principle suggested quarters. Halves would give two boxes and a weaker bound; sixteenths would give sixteen boxes and no collision at all. The quarters are chosen because four is the largest number of regions that five points must still collide in, and finding that number is the mathematics.

This is the same skill as deciding what to throw away, seen from the other end: there, the question was which features of a problem are irrelevant; here, it is which classification of the possibilities is coarse enough to force a collision and fine enough for the collision to mean something.

The generalisation nobody expects #

There is a strengthening of the principle that is genuinely surprising and is one of the deepest results in combinatorics.

Colour every pair from a group of six people red or blue — say red if they know each other and blue if they do not. Then there is always a set of three people all joined by the same colour: three mutual acquaintances or three mutual strangers.

The proof is pigeonhole applied twice. Pick a person; they have five pairs, and five pairs in two colours forces three of the same colour, say red, to three others. Now look at those three. If any pair among them is red, that pair with the original person makes a red triangle. If none is, the three form a blue triangle. Either way, done.

Six is necessary — with five people a colouring exists with no monochromatic triangle, and it is the pentagon with its diagonals. So the answer is exactly six, and this is the first case of Ramsey theory, whose slogan is that complete disorder is impossible: any large enough structure contains an orderly substructure, whether or not anyone put one there.

The costs rise appallingly fast. The number needed to force a monochromatic set of four is $18$. For five, it is unknown — somewhere between $43$ and $46$ — and Erdős’s remark stands: if aliens demanded the value for five or they would destroy the Earth, humanity should marshal every computer and mathematician; if they demanded it for six, humanity should attempt to destroy the aliens.

Where it does not apply #

The principle needs finitely many boxes, and the failure when that condition is dropped is instructive rather than merely technical.

With infinitely many boxes, more items than boxes does not force a repeat — infinite sets can be matched with proper subsets of themselves. The whole numbers can be put in one-to-one correspondence with the even numbers, which is exactly the situation the principle forbids in the finite case, and it is the same phenomenon as a punctured sphere matching an infinite plane.

That is not a small caveat. It is the boundary between two entirely different regimes, and pigeonhole is one of the cleanest statements of what makes finite sets finite: a finite set cannot be matched with a proper part of itself, and every other property in this essay follows from that.

There is a partial rescue, and it is the version that matters for analysis. Distribute infinitely many items among finitely many boxes and some box receives infinitely many — which is enough to run a great deal of the theory of sequences. Bisect an interval repeatedly, note that one half always contains infinitely many terms of a bounded sequence, and the nested halves close on a limit point. That is the Bolzano–Weierstrass theorem, and its engine is this principle applied at every step. The same instinct that puts thirteen items into twelve boxes puts a sequence into two halves and keeps the crowded one, which is how a length is pinned between two approximations rather than computed.

What the picture cannot show #

The figures show one distribution each, and the claim is about every distribution. The choice to draw the most even one is the argument’s whole strategy, and the picture cannot indicate that the drawn arrangement was chosen adversarially rather than arbitrarily — a reader who takes it as an example rather than as the extremal case has missed the point of it.

Nor can any of these figures show the applications, and the gap is wide. The pictures are of items in boxes. The results are about hair counts, decimal periods, and rational approximations to irrational numbers, and the work in each case is deciding what the boxes should be — remainders, or intervals of width $1/N$, or possible hair counts. That decision is the entire mathematical content, and once it is made the principle is trivial. A figure can only ever show the trivial half.

The ladder from here #

Rungs above: Dirichlet’s approximation theorem drawn, with the intervals and the collision. The Ramsey numbers, and the colouring of the pentagon that shows five is not enough. Erdős–Szekeres, where any sequence of $mn+1$ numbers contains a monotone subsequence — pigeonhole with a cleverer choice of box. The probabilistic method, which is pigeonhole’s descendant: prove something exists by showing a random choice produces it with positive probability, again without exhibiting one. The infinite pigeonhole principle, and what survives. The birthday problem, where the same setup is asked a probabilistic question and the answer arrives far earlier. And the handshake lemma from Königsberg, which is a counting argument of exactly this family.

Why the obvious is worth naming #

There is a general point here about what mathematics gets from stating trivialities carefully.

Nobody needs to be told that thirteen things do not fit one-per-box into twelve boxes. What is not obvious is that this observation, given a name and a habit of looking for it, settles the period of a repeating decimal, the approximability of an irrational, and the unavoidability of order in large structures. The principle contributes nothing to any of those proofs except the last line; what it contributes is the shape — the instruction to find a finite set of possibilities and count.

That is what naming a triviality is for. It converts a thing everyone already believes into a thing everyone looks for, and the looking is where the results come from.