Existence proof
Named by 48 essays across 9 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.
There is no last prime
Euclid's argument is often described as producing a new prime from any finite list. It does not, and the number it builds is frequently composite — which makes the proof more interesting rather than less.
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.
Numbers that are their own parts
Six is one plus two plus three. Twenty-eight is one plus two plus four plus seven plus fourteen. Euclid explained where such numbers come from; Euler proved there are no others of that kind; and whether an odd one exists has been open for two thousand years.
A schedule where every pair meets once
Sort n people into groups of three so that every two of them share a group exactly once. Two divisions have to come out whole, that rules out most sizes — and at every size the divisions permit, a schedule exists.
The thirty-six officers
Six regiments send six officers each, one of every rank. Arrange all thirty-six in a square so that each row and each column holds every rank once and every regiment once. Euler could not, guessed why, and was wrong about the reason.
Envy-free, up to one item
A cake can be cut anywhere, and every guarantee about fair cutting was bought with that freedom. Take the knife away and the exhaustive search over every allocation of three objects returns nothing envy-free at all — so the subject weakened the word until taking turns was enough to reach it.
Nobody has a reason to run away
A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.
Two numbers that have to meet
Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.
The value from both sides
Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.
A loop that cannot miss the middle
Feed a circle into a polynomial and a closed loop comes out. A small circle gives a loop that does not enclose the origin; a large one gives a loop that goes round it as many times as the degree. Something has to happen in between, and that something is a root.
The most area a fence can hold
One length of boundary, and the question of what shape to bend it into. The answer is a circle, everybody knows it, and the argument that convinced the nineteenth century turned out to prove something slightly different.
One line that halves them both
Two shapes lying anywhere on a page, of any sizes and any shapes at all. There is always a single straight line that cuts both of them into two equal halves at once — and finding it needs no cleverness, only the observation that a quantity which reverses sign has to pass through zero.
Three colours force a triangle
Cut a triangle into small ones and colour the corners under one restriction. However the cutting and the colouring are done, some small triangle ends up with all three colours — and the number of them is always odd.
A map that shrinks everything
One extra hypothesis — that every distance is shortened by at least a fixed factor — turns the existence of a fixed point into its uniqueness, an algorithm for finding it, and a bound on the error after any number of steps.
Always one before the double
A density says what happens on average and permits long empty stretches. This says something a density cannot — that the stretch from any number to twice it contains a prime, at every scale, without exception.
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.
A twist that cannot avoid two points
Turn the two edges of a ring in opposite directions without changing any area, and something in between must stay exactly where it is — not one point, but at least two, and the reason is that two loops enclosing the same area have to cross.
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 colouring nobody has ever seen
Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.
Three in a row on the number line
Colour the numbers one to eight in two colours and it can be arranged that no three equally spaced numbers agree. Add the ninth and it cannot. The structure being forced is arithmetic rather than graphical, and the proof is a different proof.
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.
Approached too fast to be algebraic
An algebraic number of degree d cannot be approached by fractions faster than the denominator's dth power. So a number that is approached faster than that is the root of no polynomial at all — and one can be built by choosing where its decimal digits go.
The landscape nobody is looking at
Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.
Two equilibria and no way to choose
A game can have two states nobody wants to leave, one paying more than the other, and the definition of an equilibrium has nothing to say about which happens. The two standard tie-breakers disagree, and the one that wins is usually the worse.
A mixture that is a population
A mixed equilibrium between two choosers is a knife-edge nobody has a reason to stand on. Read the same mixture as a population whose shares grow with how well they do, and it becomes a point every population is carried to — or one every population circles for ever without arriving.
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.
The table inside every quota
Give seats to districts and parties at once, and every cell of the table has a fair share it ought to round from. A table rounding every cell to its floor or its ceiling, with every total exact, always exists. The biproportional method does not always choose one: here it gives a party 2 seats where its fair share is 3.088.
Where the rounding runs out
In two dimensions a table of seats inside every fair share always exists. Add a third family of totals — every district and party split between groups — and it need not. Sixteen halves in a three-by-three-by-three table meet every total, and no whole table does it without a seat where the fair share is nothing, because the halves close a loop of seven.
Solutions that come in multiples of p
Count the solutions of x² + y² + z² = 0 in the field with five elements and there are 25; with seven, there are 49. Whenever a system of equations has more unknowns than its total degree, its number of solutions is a multiple of the characteristic — which forces a solution besides zero, and the reason is a sum over the field that vanishes because its non-zero elements form one cycle.
Two opposite points that agree twice
At any moment there are two points on opposite sides of the Earth with the same temperature and the same pressure. On a seeded globe they sit at 11.9°N 44.6°E and 11.9°S 135.4°W. The reason is the circle argument that halved two shapes, run one dimension up: the differences between opposite readings, walked round the equator, wind round zero an odd number of times — and an odd number cannot be zero.
As many cuts as colours
Two thieves steal a necklace and want half of every colour of bead each. However the beads are strung, they never need more cuts than there are colours — three cuts for three colours, four for four — and sometimes they need every one. The guarantee is the Borsuk–Ulam theorem again, with a point on a sphere read as a way of cutting the necklace, and every necklace of several small kinds has been checked against it.
Five weighings and the question is closed
Searching the triangle of splits can only ever fail to find a stable one, which is not the same as there being none. Weighing five families of coalitions against the whole settles the question outright — and the family that fails is the proof that nothing survives.
What the search has when it fails
A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.
The piece that cannot pair off
Take the sides away and the obstruction to a matching changes character completely. It is no longer a shortage of partners; it is a parity, and the quantity that measures it counts pieces of odd size rather than vertices of any size.
The reading that is almost right
Every account of simultaneous choice so far has assumed the payoffs are known to both choosers and known to be known. Replace that with each chooser seeing a private reading off by a little, and a band of equilibria closes to a single point — so the assumption nobody states decides the answer.
A count that can say zero
The branched count ends on a list of cycle shapes that passes every test and describes no covering. There is an exact formula for how many coverings a list has — a sum over the character table of a symmetric group — and it returns nought without giving any reason why.
A map that offers a choice
Brouwer's theorem needs a function, and the object it was most wanted for is not one — a best reply is a whole set whenever a chooser is indifferent. Allow a point to be sent to a set and the fixed point survives, provided the sets are convex, and the convexity is the entire hypothesis.
More blocks than points
A schedule in which every pair meets once cannot use fewer groups than it has people. Nothing about the counting conditions says so, and the proof is not combinatorial at all — it is a determinant, computed over a field the schedules have nothing to do with.
A plane in a list of numbers
A projective plane of order three has thirteen points and thirteen lines and fifty-two incidences. All of it is in the four numbers 0, 1, 3, 9 — because their pairwise differences hit every non-zero residue modulo thirteen exactly once, and the plane is that list's thirteen shifts.
Covering rather than avoiding
Two arguments say no starting guess is safe: the boundary is fractal and some regions are permanently trapped. The repair is not a better guess. It is a fixed list of starting points, computed from the degree alone, from which every root of every polynomial of that degree is found.
Three triangular numbers, and no fewer
On 10 July 1796 Gauss wrote in his diary: ΕΥΡΗΚΑ — num = Δ + Δ + Δ. Every whole number is a sum of three triangular numbers. Two are not enough, and not by a little: the numbers that are sums of two thin out to a share of nought. Both facts are statements about squares in disguise, and one picture translates them.
A ring that no pairing can break
Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.
When one of the two numbers is missing
The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.
A walk that splices in its own detours
Euler proved that a walk crossing every bridge once needs every landmass to have an even number of bridges, and then stated, without proof, that this was enough. The missing half took 137 years, and it is not an argument but a procedure: walk until stuck, notice that stuck can only mean home, and splice in a detour from anywhere with edges left. The procedure never fails, and the reason fits in one sentence about arriving and leaving.
Opposite labels that have to meet
Cut a square into triangles, label every corner +1, −1, +2 or −2, and insist only that opposite points of the edge get opposite labels. Somewhere inside, an edge must join a label to its negative. The proof counts quarter-turns round a diamond — an odd number on the boundary, zero in any triangle that avoids opposites — and making the triangles smaller turns the count back into the theorem about opposite points on the Earth.
The colours a circle forces
Take every pair from five things and join two pairs when they share nothing. Three colours are enough to colour the result so joined pairs differ, and two are not — but no triangle, no dense cluster and no counting argument explains why. The reason is five points on a circle and a direction that cannot be told apart from its opposite, and the same reason, one sphere at a time, settles Kneser's question for every size.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentNonconstructiveExhaustive searchContinuityGraphParityPigeonhole principleDegreeAntipodal pairBest replyConvexityCounterexample