Extremal Principle and Working Backwards

The extremal principle is existence-by-optimization. It proves that some pair of points is at minimum distance, that some vertex has minimum degree, that some solution has minimal $x$ — and then the argument works with that special object. On the Putnam it is often the whole proof: "let $M$ be the maximum of the $a_i$; then the equation at index $i$ gives $M \le \ldots$", and the inequality closes.

Vieta jumping is the extremal principle applied to a family of solutions, with the quadratic formula supplying the "smaller solution". Write the equation as a quadratic in $a$, note the other root $a\prime = kb - a = \frac{b^2 - k}{a}$ is an integer, show $0 \le a\prime < a$, and descend until $a\prime = 0$, which forces $k = b^2$.

Working backwards finds the proof; it is not the proof. The written solution must run from hypotheses to conclusion. The habit that makes it safe: at each backwards step, note whether the implication is reversible ("it suffices to show" is fine; "this is equivalent to" needs both directions).

The condition of a problem usually relates an object to its neighbours: an average, a distance, a count. At an ordinary object this relation says little, but at an extreme one it collides with extremality — a minimum that equals an average of values at least as large forces equality everywhere nearby, and a nearest configuration that produces a nearer one is a contradiction. The one obligation is existence: the extreme object must exist, which is automatic in a finite set or among positive integers and must be argued anywhere else.

Step 1 — the labels are positive integers, so a smallest label $m$ exists (well-ordering), attained at some point $p$.

Step 2 — at $p$: $m = \tfrac14(a + b + c + d)$ with each neighbour label $\ge m$. If any were $> m$ the average would exceed $m$. So all four neighbours have label $m$.

Step 3 — each of those neighbours is again a minimum, so the argument repeats from them. Every lattice point is reached from $p$ by a finite chain of neighbour steps, so every label is $m$. $\blacksquare$

How to find it. "Equal to the average of its neighbours" means "never strictly below all neighbours", which is only useful at a point below all of them — a minimum. Positivity and integrality are there to make the minimum exist.

Step 1 — consider all pairs $(P, \ell)$ where $\ell$ is a line through at least two of the points and $P$ is one of the points not on $\ell$. There are finitely many such pairs, and at least one (the points are not collinear). Choose the pair with the SMALLEST distance from $P$ to $\ell$.

Step 2 — suppose $\ell$ contains three or more of the points. Let $Q$ be the foot of the perpendicular from $P$ to $\ell$. Two of the points on $\ell$ lie on the same side of $Q$ (counting $Q$ itself as either side); call them $B$ and $C$ with $B$ between $Q$ and $C$ (possibly $B = Q$).

Step 3 — the line $PC$ passes through two of the points and does not contain $B$. The distance from $B$ to line $PC$ is less than the distance from $Q$ to line $PC$ (because $B$ lies on segment $QC$), which is less than $PQ$ (a leg of the right triangle $PQC$ is longer than the altitude from $Q$ — or, with $B = Q$, directly). So $(B, PC)$ is a closer pair: contradiction.

Step 4 — therefore $\ell$ contains exactly two of the points. $\blacksquare$

How to find it. Sylvester's question waited 40 years for a proof; Kelly's is the extremal principle applied to the right set — not points or lines alone but point–line PAIRS, measured by distance. When the natural objects give nothing, extremize over pairs of them.

Step 1 — induct on the odd number $n = 2k + 1$, starting at $n = 3$ ($n = 1$ is vacuous).

Step 2 — take the CLOSEST pair $A, B$. Each is the other's nearest person, so they shoot each other.

Step 3 — if anyone else also shoots $A$ or $B$, then $A$ and $B$ absorb at least $3$ of the $n$ shots, and the other $n - 2 = 2k - 1$ people receive at most $n - 3 = 2k - 2$ shots: someone among them is dry.

Step 4 — otherwise nobody else shoots at $A$ or $B$, and $A, B$ shoot only each other; so the other $2k - 1$ people shoot only among themselves, exactly as if $A$ and $B$ were absent (each one's nearest person is not $A$ or $B$). By the induction hypothesis someone among them is dry. For $n = 3$, Step 4 cannot happen, since the third person must shoot $A$ or $B$. $\blacksquare$ (For an even number of people it fails: pair everyone up in far-apart couples.)

How to find it. Shooting the nearest person is a local minimum condition; the global minimum — the closest pair — is the one configuration whose behaviour is completely determined. Removing it leaves a smaller instance of the same problem.

Vieta's formulas give the second root in two forms, and each form carries information: $a' = p - a$ shows $a'$ is an integer when $p$ and $a$ are, and $a' = \tfrac qa$ controls its sign and size. Replacing $a$ by $a'$ keeps every equation of the problem true, so solutions come in chains, and the chain moves downward when $a$ is the larger root. A minimal solution therefore has no smaller neighbour, which pins it to a small base case — and every solution descends to one of the base cases. The two checks that make it rigorous: $a'$ is a positive integer (or the case $a' \le 0$ is handled), and $a' < a$.

Step 1 — fix $k$ and suppose it is not a square. Among all pairs of positive integers with $a^2 + b^2 = k(ab + 1)$, take one with $a + b$ minimal and $a \ge b$.

Step 2 — as a quadratic in $X$, $X^2 - kbX + (b^2 - k) = 0$ has the root $a$; the other root is $a' = kb - a = \tfrac{b^2 - k}{a}$, an integer by the first form.

Step 3 — $a' \ne 0$, since $a' = 0$ would mean $k = b^2$. And $a' > 0$: if $a' < 0$, then $a'b + 1 \le 0$ and $a'^2 + b^2 = k(a'b + 1) \le 0$, impossible.

Step 4 — $a' = \tfrac{b^2 - k}{a} < \tfrac{b^2}{a} \le a$ (using $b \le a$). So $(a', b)$ is a solution in positive integers with $a' + b < a + b$: contradiction. Hence $k$ is a square. $\blacksquare$ Example: $(a, b) = (8, 2)$ gives $\tfrac{68}{17} = 4$, and the chain $(8, 2) \to (2, 0)$ ends exactly at $a' = 0$, $k = b^2$.

How to find it. The expression is symmetric and quadratic in each variable, and the claim is about $k$ alone — so fix $k$ and study the solution set as a whole. Vieta produces a new solution from any old one; the only way the descent can stop is at $a' = 0$, and $a' = 0$ is precisely $k = b^2$.

Step 1 — take a solution with $x + y$ minimal and $x \ge y$.

Step 2 — if $x = y$: $2x^2 + 1 = kx^2$, so $x^2(k - 2) = 1$, forcing $x = 1$ and $k = 3$.

Step 3 — if $x > y$: the other root of $X^2 - kyX + (y^2 + 1) = 0$ is $x' = ky - x = \tfrac{y^2 + 1}{x}$, a positive integer. Since $x \ge y + 1$, $x' \le \tfrac{y^2 + 1}{y + 1} \le y$ (the last step is $y^2 + 1 \le y^2 + y$). Then $(x', y)$ is a positive solution with $x' + y \le 2y < x + y$: contradiction with minimality.

Step 4 — so every $k$ that occurs has a minimal solution with $x = y = 1$, and then $k = 3$. Conversely $k = 3$ works: $1 + 1 + 1 = 3$. Answer: $k = 3$ only.

How to find it. Try small $k$ by computer or by hand: $k = 3$ has $(1, 1), (2, 1), (5, 2), \ldots$ and nothing else appears. The descent explains why: every solution falls to the diagonal, and the diagonal forces $k = 3$.

Backward induction is ordinary strong induction on the distance to the end: terminal positions are classified by the rules, and each other position is classified from positions nearer the end, which are already known. Its power is that it replaces a search over whole sequences of moves by a local rule. When the backward step is FORCED — only one predecessor is possible — the process can be run in reverse, and questions about reachability become questions about where the reverse run ends, as in Euclid's algorithm.

Step 1 — work up from $0$. Position $0$ is P (the player to move has lost). $1$, $3$, $4$ are N (take everything). $2$ is P (the only move goes to $1$). $5$ and $6$ are N (move to $2$). $7$ is P: its moves reach $6$, $4$, $3$, all N. $8$ is N (move to $7$), $9$ is P: its moves reach $8$, $6$, $5$, all N.

Step 2 — the pattern repeats with period $7$: P exactly when $n \equiv 0$ or $2 \pmod 7$.

Step 3 — proof by strong induction: from $n \equiv 0$ the moves reach residues $6, 4, 3$, and from $n \equiv 2$ they reach $1, 6, 5$ — never $0$ or $2$. From every other residue some move reaches $0$ or $2$: $1 \to 0$ (take $1$), $3 \to 2$ (take $1$) or $0$ (take $3$), $4 \to 0$ (take $4$), $5 \to 2$ (take $3$), $6 \to 2$ (take $4$). So the second player wins exactly when $n \equiv 0$ or $2 \pmod 7$.

How to find it. Nothing about $n = 100$ can be seen directly; everything about $n = 0, 1, 2, \ldots$ can. Compute until the pattern repeats, then prove the pattern by checking one period.

Step 1 — forwards is a branching search; backwards is forced. If $(a, b)$ with $a > b$ was reached by a move, the move must have been $(a - b, b) \to (a, b)$, because the other option would have come from $(a, b - a)$ with a nonpositive entry. Likewise for $a < b$. A pair $(a, a)$ other than $(1, 1)$ has no predecessor at all.

Step 2 — so from any $(a, b)$ there is exactly one backward path: subtract the smaller entry from the larger — the subtractive Euclidean algorithm. It ends at $(g, g)$ with $g = \gcd(a, b)$, because subtraction preserves the gcd.

Step 3 — the path reaches $(1, 1)$ iff $\gcd(a, b) = 1$. So the reachable pairs are exactly the coprime pairs, each reached in exactly one way. Example: $(5, 3) \leftarrow (2, 3) \leftarrow (2, 1) \leftarrow (1, 1)$.

How to find it. Two forward choices per step make an exponentially branching tree; one backward choice per step makes a path. When the forward direction branches, check whether the backward direction is forced.

Step 1 — write heap sizes in binary and let $s$ be their XOR (add the binary digits without carrying). Claim: the player to move loses iff $s = 0$.

Step 2 — the empty position has $s = 0$ and is a loss for the player to move, matching the claim. From $s = 0$, any move changes one heap, hence changes $s$: every move goes to $s \ne 0$. From $s \ne 0$, let $d$ be the highest binary digit of $s$; some heap $h$ has a $1$ in position $d$, and $h \oplus s < h$ (the digit $d$ turns off, higher digits are unchanged). Reducing $h$ to $h \oplus s$ is a legal move and makes the new XOR $s \oplus s = 0$.

Step 3 — by backward induction on the total number of coins, $s = 0$ positions are losses and $s \ne 0$ positions are wins.

Step 4 — heaps $3 = 011_2$, $5 = 101_2$, $7 = 111_2$: $s = 001_2 = 1$. Every heap has its last digit $1$, so there are three winning moves: $3 \to 2$, $5 \to 4$, $7 \to 6$ (each takes one coin), and each leaves XOR $0$: $2 \oplus 5 \oplus 7 = 0$, $3 \oplus 4 \oplus 7 = 0$, $3 \oplus 5 \oplus 6 = 0$.

How to find it. Classify small positions backwards: one heap is a win, two equal heaps are a loss (copy the opponent), $(1, 2, 3)$ is a loss. The losses are exactly the positions whose heaps "cancel" in binary — and XOR is the operation that expresses cancelling.