The Kill Shots

Some tools build a solution piece by piece. These five end the fight outright. A kill shot is a single observation that makes an exponential search unnecessary: one line where a machine, working without the abstraction, would drown in cases.

Each tool gets the same treatment: a definition, which every textbook has; a recognition signal, which textbooks leave tacit — the smell a trained mind notices, often pre-verbally, before the hand reaches for the tool; a worked pair, one teachable in a sitting (★★), one at genuine olympiad level (★★★★); and a line on how machines fare. The signals are the real payload. Learn the smell, and the tool fires itself.

Pigeonhole

The tool. Put more than n objects into n boxes and some box holds at least two. In general, n objects in k boxes put at least ⌈n/k⌉ into some box. That is the entire theorem. Its power lives in the choice of boxes — which is never given in the problem. It must be invented.

The smell. "Prove there exist two…" or "show that some…" with no obvious construction. A quantity bound: "among any 51 numbers…", "any five points in a square…". A guarantee demanded no matter how an adversary arranges things. The trained reflex: what finite set of categories can I force these objects into? Distances suggest geometric cells; divisibility suggests residues or odd parts; sequences suggest prefix sums. Two Londoners have the same number of head hairs — nine million people, at most about a million possible hair counts; the boxes are the counts. Any 100 integers contain a consecutive block summing to a multiple of 100 — the boxes are the residues of the 101 prefix sums S₀, …, S₁₀₀; two collide, and the block between them is their difference. Aimed at the continuum, the same one-liner invents rational approximation: Dirichlet's theorem — for any real α some q ≤ N has |qα − p| < 1/N — is N + 1 fractional parts falling into N intervals.

★★ · Five Points in a Square

Prove that among any five points in a closed unit square, two lie at distance at most √2/2 ≈ 0.707.

Pause here. The page can wait.

Solution. Cut the square into four ½ × ½ quadrants. Five points, four quadrants: some quadrant holds two of them. Two points of a ½ × ½ square are at most a diagonal apart: √((½)² + (½)²) = √2/2. ∎

Nothing in the statement mentions quadrants. The solver manufactures the boxes so that "same box" forces the conclusion — and the choice of four boxes, not nine and not two, is reverse-engineered from the number five: one box fewer than the points.

The Move — Manufacture the boxes. The theorem is free; the boxes are the work. Read the conclusion you want, then invent categories in which a collision delivers it.

★★★★ · The Unavoidable Run

Prove that every sequence of n² + 1 distinct real numbers contains a monotone subsequence — increasing or decreasing — of length n + 1.

Try it before reading on. The boxes are well hidden.

Solution. To each position i attach a two-number label (xᵢ, yᵢ): the length of the longest increasing subsequence ending at i, and of the longest decreasing one ending there. Suppose no monotone subsequence reaches length n + 1. Then every xᵢ and yᵢ lies in {1, …, n}: at most n² distinct labels for n² + 1 positions. Pigeonhole: two positions i < j share a label. But the numbers are distinct, so either aᵢ < aⱼ — and any longest increasing run ending at i extends by aⱼ, forcing xⱼ ≥ xᵢ + 1 — or aᵢ > aⱼ, forcing yⱼ ≥ yᵢ + 1. Either way the labels differ. Contradiction. ∎

This is Erdős–Szekeres (1935), carrying the setter's tell from Chapter 8: "n² + 1 terms" is strange exactness — n² terms can dodge, via n descending blocks of n, each block higher than the last. The boxes here are pairs of statistics about the object itself: nobody "sees" n² boxes in the statement; the solver builds a two-coordinate fingerprint precisely so that a collision is impossible, then counts fingerprints. A companion classic on the same fuel: any n + 1 numbers from {1, …, 2n} include one dividing another — write each as 2ᵏ·m with m odd; only n odd parts exist; two numbers share one, and the smaller-powered divides the other.

The Move — Fingerprint and collide. Attach monotone statistics until a collision would be absurd; then force the collision by counting. The double-label trick recurs all over combinatorics.

Machines and this move. Verifying a pigeonhole proof is trivial, but finding the boxes is invention over an infinite space of partitions — and Haken proved in 1985 that resolution proof systems, the engine inside classical SAT solvers, need exponentially long proofs of the pigeonhole formula itself. One human abstraction, one exponential wall bypassed.

Invariants & Monovariants

The tool. An invariant is a quantity no legal move can change — a conserved charge. To prove a target unreachable, exhibit an invariant that differs between start and target. A monovariant moves in one direction only; use it to prove a process must stop, and to see where it can end. This is the move that killed the 14–15 swap in Chapter 2: permutation parity times blank-row parity never changes, so Loyd's thousand-dollar prize was never in danger.

The smell. The problem describes moves — "erase two numbers and write…", "two chameleons meet and…", "flip any row" — and asks can you reach this? does it stop? what are the possible ends? The reflex chain: compute a few cheap quantities (sum, sum mod 2, mod 3, sign of the product, inversion count) before and after one generic move; whatever survives unchanged is your candidate. For termination, hunt a bounded quantity forced monotone. The deep habit: ignore the trajectory entirely and study what the dynamics conserve — Noether's instinct in miniature.

★★ · The Blackboard Reduction

The numbers 1 through 10 stand on a blackboard. A move: erase any two of them, a and b, and write |a − b|. After nine moves a single number remains. Can it be 0?

Pause. Play a few moves in your head first.

Solution. Track S, the sum of everything on the board, mod 2. A move changes the sum by (a + b) − |a − b| = 2·min(a, b) — an even number — so S mod 2 never changes. It starts at 1 + 2 + ⋯ + 10 = 55, odd. The final number is therefore odd, and in particular never 0. ∎ (Odd endings are achievable down to 1; the invariant says exactly which endings are barred.)

The reachability graph of this game has thousands of states. The invariant collapses it to two.

The Move — Find the conserved charge. Decide reachability without exploring a single branch: compute what every move preserves, then compare start with target.

★★★★ · The Pentagon That Must Stop

(IMO 1986, Problem 3.) Integers x₁, …, x₅ sit at the corners of a pentagon, with total sum s > 0. Whenever some corner value y is negative, you may replace its consecutive triple (x, y, z) by (x + y, −y, y + z). Prove that this procedure necessarily terminates.

Pause here — check first what a move leaves alone.

Solution. The move conserves the total: (x + y) + (−y) + (y + z) = x + y + z. So the sum stays s > 0 forever. Now define f(x₁, …, x₅) = Σᵢ (xᵢ − xᵢ₊₂)², indices mod 5 — a nonnegative integer. Apply the move at position 4 (cyclic symmetry makes that typical), with y = x₄ < 0. Four of f's five terms change; (x₃ − x₅)² survives, since both its endpoints shift by y. Expanding the four affected squares and cancelling:

Δf = [−2y(x₁ − x₃) + y²] + 4x₂y + 4x₁y + [2y(x₅ − x₂) + y²] = 2y(x₁ + x₂ + x₃ + x₅) + 2y² = 2y·s.

Since y < 0 < s, every move strictly decreases f. A strictly decreasing nonnegative integer allows only finitely many moves. ∎

Now the honest part: nobody derives f by pure taste in an exam room; you hunt. You want a nonnegative integer that provably drops; sums and linear forms are conserved — useless — so you try the natural quadratic forms, Σxᵢ², Σ(xᵢ − xᵢ₊₁)², Σ(xᵢ − xᵢ₊₂)², computing Δ for each until one factors through s. In 1986, only eleven students solved this problem. The gap between checking an invariant and inventing one is the gap between ★★ and ★★★★.

A companion drill: 13 red, 15 green, 17 blue chameleons; when two of different colors meet, both turn the third color. All-one-color is impossible — every meeting shifts each pairwise difference of counts by 0 or ±3, so the differences mod 3 are conserved; they start at 2, 2, 1, and a monochrome state needs a 0.

The Move — When nothing is conserved, find what only falls. Termination wants a bounded monotone quantity. Hunt it in a parametrized family and let the algebra pick the member.

Machines and this move. Checking an invariant is one line of algebra; discovering one is synthesis over an infinite function space — the same problem, called loop-invariant inference, is still a benchmark bottleneck in program verification, and language models do well on famous invariants and poorly on freshly minted dynamics.

The Extremal Principle

The tool. Interrogate an extreme witness: the largest, smallest, first, closest, boundary case. Mode one — structure: the extremal object's extremality forbids certain configurations around it, which is exactly the leverage you need. Mode two — minimal counterexample, Fermat's descente infinie: assume a counterexample exists, take the smallest, construct a smaller one; therefore none exists. Descent in one breath: if √2 = a/b with b minimal, then a² = 2b² forces a = 2c, whence 2c² = b² — and (b, c) is a strictly smaller representation. Dead. The same skeleton disposes of x⁴ + y⁴ = z⁴, Fermat's own showcase.

The smell. "There exists an element with property P" in a finite mess — first ask whether the maximum or minimum has P for free. Any configuration where "pick the worst offender and improve it" seems available. Geometry with closest pairs, smallest circles, minimal angles. Before inventing machinery, ask what the extremal element already knows: an extremum ships with a free contradiction generator, since anything more extreme than it is impossible by fiat.

★★ · The Tournament King

In a round-robin tournament — every pair plays once, no draws — prove there is a player v such that every other player either lost to v, or lost to someone who lost to v.

Pause. Whom would you nominate?

Solution. Nominate v, a player with the maximum number of wins. Suppose some u is not reachable in two steps: then u beat v, and u also beat every player v beat — for if v beat w and w beat u, u would be reachable. So u's victims include all of v's victims plus v himself: wins(u) ≥ wins(v) + 1, contradicting maximality. ∎

No induction, no construction, no algorithm. The maximal element is forced to have the property, because a violation would manufacture something greater than the maximum.

The Move — Ask what the maximum already knows. One extremal choice replaces an entire search.

★★★★ · Sylvester's Line

A finite set of points in the plane is not all on one line. Prove that some line through two of the points contains no third point of the set. (Sylvester posed it in 1893; it stood open for about forty years. The proof below is L. M. Kelly's — widely called a proof from The Book.)

Pause. What would you minimize?

Solution. Consider all pairs (P, ℓ) where ℓ is a line through at least two points of the set and P is a point of the set not on ℓ. Such pairs exist, since the set is not collinear, and there are finitely many — so choose the pair minimizing the distance from P to ℓ. Claim: ℓ carries exactly two points. Suppose it carried three. Drop the perpendicular from P to ℓ, with foot F. Of the three points, two lie on the same closed side of F: call them A (nearer F, possibly at F) and B (farther), so the order along ℓ is F, A, B with A ≠ B. A is not on the line PB — otherwise PB would meet ℓ twice and P would lie on ℓ. Now double-count the area of triangle ABP: ½·|AB|·d(P, ℓ) = ½·|PB|·d(A, PB), so d(A, PB) = d(P, ℓ)·|AB|/|PB|. But |PB| = √(PF² + FB²) > FB ≥ AB, since P is off the line (PF > 0) and B lies beyond A (FB ≥ AB). Hence d(A, PB) < d(P, ℓ): a point–line pair closer than the minimum. Contradiction. ∎

Forty years of failed attacks, then half a page whose only idea is choosing what to minimize — and the craft is the choice: a joint point–line object, neither alone. "How would I ever find this?" The honest answer is a checklist, run the way a chess player enumerates checks: closest pair? smallest angle? minimal area? minimal point–line distance?

The Move — Choose what to minimize. The extremal principle is only as strong as the functional you hand it. Enumerate candidates deliberately.

Machines and this move. Computing an argmax is instant; wielding extremality as a proof lever means inventing the thing to extremize — the pigeonhole-box bottleneck again; descent's orderings are the "termination measures" automated verifiers still need humans to supply.

Symmetry & Pairing

The tool. Exploit a transformation that preserves the problem. Three workhorse forms. Pairing: match objects so each pair carries a constant or cancelling contribution. Mirroring: in games, answer every opponent move through a symmetry, so the future is pre-answered. Strategy stealing: a symmetry between the players shows the first player's extra move can never hurt — so a first-player win exists, exhibited or not.

The smell. Terms in complementary pairs — k with n + 1 − k, a subset with its complement, a divisor d with n/d. A center, an axis, an involution: an operation that undoes itself. "Who wins with perfect play?" on a symmetric board. The reflex: hunt for an involution and ask what its fixed points are. Sums collapse; existence proofs fall out of the unpaired elements. (The most famous pairing in mathematics is a schoolroom legend about young Gauss; the story — and what is wrong with it — closes Chapter 11.)

★★ · Coins on a Round Table

Two players alternately place identical circular coins on a round table; coins may not overlap. Whoever cannot move loses. Who wins?

Pause. The table is round for a reason.

Solution. The first player — by seizing the one self-symmetric point. Move 1: a coin dead center. Thereafter, mirror: whenever the opponent plays at a spot S, reply at S′, its 180° rotation about the center. The invariant: after each of your moves, the whole configuration is symmetric under that rotation. So when the opponent finds any legal spot S, its mirror S′ is empty — the position was symmetric before their move — and legal, since it clears the mirror image of everything S cleared; and S′ ≠ S, because the rotation's only fixed point, the center, was taken on move one. The table is finite, so someone runs out of moves. It is never you. ∎

The mirroring player never calculates. The symmetry answers every future question in advance — a complete strategy compressed into one sentence.

The Move — Seize the fixed point, then mirror. Whoever owns the symmetry owns the endgame.

★★★ · Nim, or Mirrors Made of Bits

Three piles of stones: 3, 4, 5. A move takes any positive number of stones from any one pile. Taking the last stone wins. Who wins, and how?

Stop. Play the two-pile version first — say 2 and 2.

Solution. Two equal piles fall to pure mirroring: the second player repeats each move on the other pile, restoring (n, n) after every turn — a reply always exists, so the last stone is theirs. Unequal piles: the first player equalizes, then becomes the mirror.

Bouton's theorem (Charles Bouton, 1901 — the analysis that founded combinatorial game theory) generalizes the mirror to any number of piles. Write the pile sizes in binary. A position is lost for the player to move exactly when every binary column contains an even number of 1s — equivalently, when the XOR of the pile sizes, the nim-sum, is 0. Both directions take one observation each. From a zero position, any move edits a single pile, flipping at least one bit — some column goes odd; the balance always breaks. From a nonzero position, look at the highest unbalanced column; some pile has a 1 there; shrinking that pile to (itself XOR the nim-sum) rebalances every column — and it is a genuine shrink, because its leading change turns a 1 into a 0. The empty position has XOR 0, and its mover has already lost. So the winning policy is simply: always hand your opponent a zero.

Here: 3, 4, 5 = 011, 100, 101. The XOR is 010 ≠ 0, so the first player wins. The twos column is the unbalanced one, and only the 3-pile has a 1 there: play 3 → 3 ⊕ 2 = 1. Check: 001, 100, 101 — every column even. It is the only winning opening; balancing through the 4-pile or 5-pile would require them to grow. ∎

The equal piles were the special case the mirror explained: (n, n) is balanced column by column. Bouton's zero is mirroring generalized — when the board offers no geometric symmetry, build an arithmetic one and keep it balanced.

The Move — Pair the bits. The involution can live in the arithmetic rather than on the board. Find the quantity whose balanced states you can always restore and your opponent can never preserve.

★★★★ · Chomp, and the Stolen Strategy

Chomp (David Gale, 1974): an m × n chocolate bar, mn ≥ 2, with the bottom-left square poisoned. A move: choose any remaining square and eat it together with every square above and to the right of it. Whoever eats the poison loses. Prove the first player wins — for every board size — even though no general winning strategy is known.

Pause here. You will not find the strategy. That is the point.

Solution. Chomp is finite, deterministic, perfect-information, and cannot draw — so by backward induction (Zermelo), exactly one side owns a winning strategy. Suppose it is the second player. Let the first player open with the smallest possible nibble: the single top-right square. By assumption the second player has a winning reply Y, leading to some position Q whose mover — player one — loses. But observe: every Chomp move removes the top-right square anyway. So Q is exactly the position reached if Y had been played as an opening move. Player one could therefore have opened with Y, seating player two on the losing side of Q. Contradiction — so the winner is player one. ∎ The proof names no strategy, and for general boards the winning first move is still unknown, computed only for small cases.

The symmetry here is between the players: anything your winning reply achieves, I could have achieved one move earlier. The same skeleton gives Nash's argument for Hex — an extra stone never hurts — and tic-tac-toe's "the first player does not lose."

The Move — Steal the strategy. Prove the win exists by pre-empting the second player's hypothetical strategy. Existence without exhibition.

Machines and this move. Engines detect and exploit board symmetries for pruning, but strategy stealing is a proof that needs zero search and yields zero policy — a reinforcement learner can master playing Chomp and still cannot say why player one wins.

Coloring & Parity

Chapter 6 ended on a broken chessboard: two opposite corners gone, thirty-one dominoes offered, and a two-sentence refusal — every domino covers one dark square and one light one, and the two missing corners shared a color. Take the generalization now, because it is a whole arsenal. The tool: assign each cell a color or weight so that (a) every piece, wherever it lands, covers a fixed color pattern, while (b) the board's total color count is one the pieces cannot compose. A coloring is a homomorphism: it maps a vast space of attempted tilings onto tiny arithmetic — counts mod k — where the impossibility becomes visible. Parity arguments are the two-color special case; the whole device is this chapter's conserved charge specialized to tilings — an invariant wearing pigment.

The smell. Tiling and covering questions; traversals on grids — knight tours, lamp-flipping games; and above all this signature: the area arithmetic says possible while every attempted construction stubbornly fails. That stubbornness is the smell of a hidden obstruction. The reflex: try the chessboard coloring, then stripes, then diagonals mod k — with k matched to the tile's length. Tune the pigment's period to the piece's footprint.

★★ · Twenty-Five T's

Can twenty-five T-tetrominoes tile a 10 × 10 board? (Area check: 25 × 4 = 100. Arithmetic has no objection.)

Pause. Color first, then count.

Solution. Chessboard-color the board: 50 dark squares, 50 light. Wherever a T-tetromino lands, it covers three squares of one color and one of the other — an odd number of dark squares either way. Twenty-five T's therefore cover a total number of dark squares that is a sum of twenty-five odd numbers: odd. But the board has exactly 50 dark squares — even. Impossible. ∎

The Move — Let parity see what area cannot. When the counts pass and the constructions keep failing, a two-coloring often knows why.

★★★★ · The Ten-by-Ten That Refuses

Prove that a 10 × 10 board cannot be tiled by twenty-five straight tetrominoes — 1 × 4 tiles. (The area check passes again. The trap is armed.)

Pause here. The chessboard pigment is too coarse for this one.

Solution. Color cell (i, j) — rows and columns counted from 0 — with (i + j) mod 4: diagonal stripes of period four. Key property: a straight tetromino, horizontal or vertical, occupies four cells whose (i + j) values are consecutive — hence exactly one cell of each color 0, 1, 2, 3. So twenty-five tiles would cover each color exactly 25 times: a tiling forces 25 cells of every color. Now census the board. Among i ∈ {0, …, 9}, the residues 0 and 1 occur three times each ({0, 4, 8} and {1, 5, 9}), residues 2 and 3 twice each; likewise for j. Counting cells with (i + j) ≡ r means convolving c = (3, 3, 2, 2) with itself:

• color 0: 3·3 + 3·2 + 2·2 + 2·3 = 25
• color 1: 3·3 + 3·3 + 2·2 + 2·2 = 26
• color 2: 3·2 + 3·3 + 2·3 + 2·2 = 25
• color 3: 3·2 + 3·2 + 2·3 + 2·3 = 24

(Sanity: 25 + 26 + 25 + 24 = 100 ✓.) Colors 1 and 3 hold 26 and 24 cells — not 25. No tiling exists. ∎

The coloring is engineered to the tile: period-four diagonals because the tile has length four and must eat one cell of each color. (The general theorem lurking behind the trick — de Bruijn, 1969: an a × b rectangle can be tiled by 1 × n exactly when n divides a or b.) The ★★★★ skill is not applying a coloring. It is designing one whose arithmetic the tile respects and the board violates.

One warning about scope: colorings prove only impossibility. Possibility needs a construction — and Chapter 10 opens with the construction machine.

The Move — Engineer the coloring to the tile. Match the pigment's period to the piece's footprint, then count what the board actually has.

Machines and this move. A non-tileable board is a SAT solver's worst case — John McCarthy circulated the mutilated chessboard as a "tough nut" for proof procedures — yet the coloring certificate, once conjectured, is machine-checkable in microseconds. Conjecturing it is the human part.

The five, at a glance

Five ways to end a fight before it starts — each replacing a search with an observation, which is exactly why machines find them hardest to originate and easiest to check. The next chapter's tools do the opposite kind of work. They build.