Pigeonhole principle
Named by 20 essays across 8 fields — each of them below, with the objects they name alongside it.
More things than boxes
If there are more objects than containers, some container holds two. That is the entire principle, it is impossible to disagree with, and it settles questions that look nothing like it.
Six people at a party
Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.
How close a fraction can get
Drop eight points into seven boxes and two of them share. That one line, applied to the multiples of an irrational number, proves that every irrational has infinitely many astonishingly good rational approximations — and no construction is needed anywhere.
The seat that vanishes when the house grows
Twenty-seven whole seats have to be divided between five regions whose exact shares are 15.417, 7.209, 1.755, 1.431 and 1.188. Every rule for rounding those five numbers breaks something, and the instance drawn here breaks all three of the classical ways at once.
One bottleneck and nothing else
A set of jobs can be filled by distinct people unless some group of jobs has too few candidates between them — and that single obstruction is the only one there is, which is what makes the theorem worth having.
Eighteen people, and the seventeen that escape
Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.
The sequence that cannot avoid a staircase
Any ten numbers in a row contain four that climb or four that fall. The proof gives every term a pair of counters, notices that no two terms can share a pair, and is finished — with a bound that is exactly right.
One point in every big enough shape
A determinant measures a lattice, not the basis that happened to describe it — and that measurement is an exchange rate. Any symmetric convex region with more than four times that area has to swallow a lattice point.
On the circle and never home
Every root of unity lies on the unit circle, and so does the point (3 + 4i)/5 — yet no power of it ever returns to 1. A root of a whole-number polynomial of degree ten does the same. What forces a point home is a condition on the numbers its polynomial ties it to, and how far one of them may stray is a question open since 1933.
The subsequence that has to exist
Every bounded list of numbers has a part that settles down. A bounded list of functions need not: the waves sin 2πkx never come within 1.76 of one another. One extra condition — that no member may change faster than a bound they all share — restores the guarantee, and it is the reason a differential equation with a continuous rule has a solution at all.
A failed search is a proof
Search for an assignment by branching on variables and backing up whenever a clause turns false. If every branch fails, the tree the search leaves behind is itself a resolution refutation: write at each branch point the resolvent of the clauses below it, and the top of the tree is the empty clause. So every limit on short refutations is a limit on every such search — and the pigeonhole clauses, whose refutations are long, defeat them all.
Why the expansion has to repeat
The continued fraction of √61 runs 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 and then starts again. It must: each step's state is a pair of whole numbers trapped in a small band, and only 14 pairs fit. The expansion of √61 visits 11 of them in a cycle, the other 3 form a cycle of their own, and the period reads the same backwards before its last term, which is twice the first.
A collision that finds a factor
A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.
A filter that changes only the spread
The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.
Twenty cards with no set among them
The card game SET is a four-dimensional space over the integers mod 3, and a set is a line in it. Twenty cards can avoid every line and twenty-one cannot — a fact that took a proof in 1970 — while laying cards down at random and stopping when nothing more fits reaches twenty about once in two thousand tries.
The polynomial that bounds the caps
For forty years the best bound on a set of SET cards with no set among them shrank only like one over the dimension. In 2016 a two-page argument made it shrink exponentially, and the whole proof is a count of monomials: a table that is diagonal on a cap, one polynomial that describes it, and the fact that three parts of a degree cannot all be large.
No table of truth values is enough
Two truth values decide classical logic. Gödel asked in 1932 whether some longer list of values could decide the constructive system, and answered with a pigeonhole: with n values, some two of n + 1 statements must share one, so a formula saying exactly that holds in every n-valued table and is not a theorem. The chains of truth values then descend forever, and what they share is a logic of its own — the logic of the real interval.
Enough partners in every finite group
Hall's theorem says a matching exists unless some group has too few partners between them. On an infinite graph that is false: one vertex that can be paired with anybody, and every other with exactly one, passes the test on every finite group and has no matching at all. The failure needs a vertex with infinitely many choices. Forbid that, and the theorem comes back, by an argument about trees rather than about matchings.
Every crowd holds a bowl or a dome
Among enough points in the plane, some k of them always bend upward like a bowl or some l bend downward like a dome. The number that forces it is a binomial coefficient, it is exactly right, and it proves that every large enough crowd contains a convex polygon — with a bound nobody could lower to the true answer for eighty years.
Half the neighbours forces a tour
Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentExistence proofExhaustive searchNonconstructiveFinite fieldGraphRamsey numberBasisBipartite graphCap setCollisionCompactness