Week 15 · Part 1 — The Invariant Method

Every induction proof at AIMO level follows this rigid structure. Memorise the sentences word-for-word.

Worked example — sum of first $n$ squares

Claim. $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$.

Base case. $n = 1$: LHS $= 1$, RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$. ✓

Inductive step. Assume $1^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}$. Then: $$ 1^2 + \cdots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}, $$ which is the RHS at $n = k+1$. ✓

Conclusion. By induction, the formula holds for all $n \ge 1$. $\blacksquare$

Worked example — $\sqrt{2}$ is irrational

Suppose for contradiction that $\sqrt{2} = p/q$ where $p, q$ are integers with $\gcd(p,q) = 1$ and $q \neq 0$.

Then $p^2 = 2q^2$, so $p^2$ is even, hence $p$ is even. Write $p = 2m$. Then $4m^2 = 2q^2$, so $q^2 = 2m^2$ is even, hence $q$ is even.

But then $\gcd(p, q) \ge 2$, contradicting $\gcd(p, q) = 1$. $\blacksquare$

Pigeonhole principle. If $n+1$ objects are placed into $n$ boxes, at least one box contains 2 or more objects.

Generalised form. If $kn + 1$ objects are placed into $n$ boxes, at least one box contains $k+1$ or more objects.

Pigeonhole proofs are often used alongside invariant arguments — the invariant restricts the reachable space, and pigeonhole shows that within that space some property must hold.

Mini-example

Among any 13 people, at least 2 share a birth month (12 boxes, 13 pigeons). Among 25, at least 3 share a month ($25 = 2 \cdot 12 + 1$).

Invariant: a quantity $Q$ attached to a state $S$ such that, after any allowed operation $S \to S'$, we have $Q(S) = Q(S')$. If $Q(\text{start}) \neq Q(\text{target})$, the target is unreachable.

Picture 1 — Parity Invariant (Chess King)

Picture 2 — Modular Clock

Picture 3 — Invariant on a Graph (vertex labels)

Four families of invariant

Setting. Configuration of 0/1 cells; allowed operation flips a specific pattern (e.g. an adjacent pair).

Derivation. Flipping cell $i$ changes $x_i \in \{0,1\}$ by $\pm 1$. Flipping two cells changes the total sum by $-2, 0$ or $+2$. In all cases, sum mod 2 is fixed. $\square$

Setting. Chips on a cycle of length $n$; operation moves chips between adjacent cells.

Worked variant. If the operation requires moving two chips in opposite directions simultaneously, then $T$ changes by $+1 - 1 = 0$ — $T \pmod n$ is invariant. So a configuration with $T$ summing to a different residue is unreachable. $\square$

Setting. A frog hops on a number line; from $x$ it jumps to $x+2$ or $x-3$.

Derivation. If $w_i$ are weights and operation $j$ shifts a value $v_a$ to $v_a + \delta_j$ at cell $a_j$, the weighted sum changes by $w_{a_j} \delta_j$. Choose weights so all $w_{a_j}\delta_j$ are equal mod some $n$, or zero — that produces a (semi-)invariant. $\square$

Problem. An $8 \times 8$ chessboard has the two opposite corner squares (top-left and bottom-right) removed. Can the remaining 62 squares be tiled by 31 dominoes (each domino covers two adjacent squares)?

Observe

• Standard chessboard colouring: 32 black + 32 white squares.
• The two opposite corners are the same colour (top-left and bottom-right are both, say, white).
• After removal: 30 white + 32 black squares.
• Each domino covers 1 black + 1 white.

Strategy

Find an invariant: the difference $B - W$ in the remaining region, where each domino changes neither count (it removes 1 of each). If we could tile completely, we'd need $B = W$. But $B - W = 2 \neq 0$. Impossible.

Proof

Colour the chessboard alternately black/white in the usual pattern. Let $B$ = number of black squares remaining, $W$ = number of white. Initially $B - W = 0$. After removing two same-colour (white) corners, $B - W = 2$.

Every domino covers two adjacent squares which differ in colour, so it covers exactly 1 black and 1 white square. Hence each domino placed reduces both $B$ and $W$ by 1, leaving $B - W$ unchanged — an invariant.

If the 62 squares were fully tiled by 31 dominoes, we would have $B = W = 0$, so $B - W = 0$. But the invariant says $B - W = 2$. Contradiction. Hence no such tiling exists. $\blacksquare$

Problem. Chips sit on the vertices of an $n$-cycle ($n \ge 3$). Operation: pick a vertex with at least 2 chips; remove 2 chips from it and add 1 chip to each neighbour. Prove that the total number of chips modulo $n$ is preserved? — actually, prove that the "position-weighted total" $T = \sum_c \text{pos}(c) \pmod n$ is invariant.

Observe

• Fire vertex $i$: lose 2 chips at $i$, gain 1 at $i-1$ and 1 at $i+1$ (mod $n$).
• $\Delta T = -2 \cdot i + 1 \cdot (i-1) + 1 \cdot (i+1) = -2i + i - 1 + i + 1 = 0$.

Proof

Define $T = \sum_{c \text{ chip}} \text{pos}(c) \pmod n$, where pos$(c)$ is the cycle-position label of the vertex holding chip $c$.

The firing operation at vertex $i$ removes two chips with position $i$ and adds one chip at position $i-1$ and one at position $i+1$ (all mod $n$). Hence $$ \Delta T = (i-1) + (i+1) - 2i = 0 \pmod n. $$ Therefore $T \pmod n$ is invariant under every legal firing. $\blacksquare$

Problem. A row of 7 coins, all showing heads (H). Operation: flip any adjacent pair of coins. Prove that the all-tails (TTTTTTT) configuration is unreachable.

Observe

• Initial: 7 heads, 0 tails. Number of tails = 0.
• Each operation flips 2 coins; the parity of the tail-count changes by $-2, 0,$ or $+2$, so its mod 2 stays the same.
• So tail-count mod 2 is invariant.
• Initially 0 ≡ 0 (mod 2). Target 7 ≡ 1 (mod 2). Contradiction.

Proof

Let $T$ = number of coins showing tails. Initially $T = 0$. Each operation flips two coins. For each coin flipped, the contribution to $T$ changes by $+1$ if it was heads and now tails, or $-1$ if it was tails and now heads. Hence per coin, $\Delta T \in \{+1, -1\}$. Across two coins, $\Delta T \in \{-2, 0, +2\}$. Therefore $T \pmod 2$ is invariant.

Starting from $T = 0$ (even), we can never reach $T = 7$ (odd). $\blacksquare$

Problem (preview). Words in alphabet $\{A, B\}$. Operation: replace any occurrence of $AB$ by $BBA$, or $BA$ by $AAB$ (or some variant). Prove an invariant.

Approach

Let $\#A$ = number of A's, $\#B$ = number of B's, and $I = $ "number of $A$'s lying to the left of each $B$" (i.e. inversion-like count). Under operation $AB \to BBA$, we lose one inversion if $B$ moves left of $A$. Track $\#A$ and $\#B$ separately; check $(\#A) \pmod 2$ and $(\#B) \pmod 2$ across replacements.

Sketch proof

If the operation is $AB \to BBA$: $\#A$ goes from $a$ to $a$ (no change), $\#B$ from $b$ to $b+1$ (changes by 1). So $\#A$ is invariant; $\#B \pmod{\text{something}}$ may be a semi-invariant.

The deep observation (used in AIMO 2022 Q8) is that both $\#A$ and a positional weighted sum like $\sum_{i \in B} 2^i \pmod{\text{prime}}$ become a precise invariant. This problem's answer is $\boxed{512}$ valid words reachable from the starter — the count is $2^9$ because nine bits of freedom remain after invariants are pinned. $\blacksquare$

Problem. A 4×4 grid contains 16 lamps, initially 15 off and 1 on (top-left). Operation: pick a row or column and flip every lamp in it. Can we reach the configuration "all 16 on"?

Two invariants together

1. Sum of all lamps mod 2: each row/column flip toggles 4 lamps, so the parity of the on-count changes by $\pm 4 \equiv 0 \pmod 2$. Hence sum mod 2 is invariant. Initial = 1 (odd). Target = 16 (even). Contradiction. Unreachable.

The single parity invariant already kills the problem — but in harder variants you may need to combine row-parities AND column-parities. $\blacksquare$

An $3 \times 3$ board has the centre square removed. Can the 8 remaining squares be tiled by 4 dominoes? Argue using parity colour invariant.

A frog starts at $0$. Each step it jumps $+2$ or $-3$. Can it reach position $100$? Position $101$?

Enter 1 if reachable, 0 if not for each:

Pos 100:

Pos 101:

Ten coins in a row, all heads. Operation: flip any three consecutive coins. Can we reach all tails?

The numbers $1, 2, 3, \ldots, 100$ are on a blackboard. Operation: pick any two numbers $a, b$, erase both, write $|a-b|$. Repeat until one number remains. Is that final number odd or even? Prove it.

Consider a 2×2 puzzle: positions labelled 1,2,3 and a blank. Tiles can slide into the blank. Starting from $\begin{pmatrix}1 & 2\\ 3 & \_\end{pmatrix}$, can we reach $\begin{pmatrix}2 & 1\\ 3 & \_\end{pmatrix}$? (i.e. swap just 1 and 2.)

Problem. 7 chips sit at positions $0, 1, 2, 3, 4, 5, 6$ on a number line (one per position). Operation: pick chips at positions $i$ and $j$ with $i < j$; move the chip at $i$ to $i+1$ and the chip at $j$ to $j-1$ (chips may stack). Prove: the total sum of positions is invariant, hence determine the minimum-spread (all chips coincide) configuration is at position $3$.

Tap stars to record your confidence on each atomic skill. Saved to local browser storage.

Mistakes you made on AIMO problems are saved below. Review before next session.

• You now know 4 families of invariant: parity, modular, weighted-sum, combinatorial.
• The detection framework is universal: find $Q$ → prove preservation → compare endpoints.
• Next (Part 2): Extremal Principle & Monovariants — quantities that always decrease, used to prove termination.

Problem. Three piles of stones contain $a, b, c$ stones. Operation: pick any two piles, transfer one stone from one to the other. Determine all pairs of starting/ending configurations that are mutually reachable.

Observe

• Total sum $a + b + c$ is invariant under every operation.
• Suppose we can swap freely — what else might be conserved?
• Notice no positional structure; just three labels.

Proof

Each operation preserves $a + b + c$. We claim no further invariant exists: any two configurations with the same total are mutually reachable.

Reachability. Given $(a, b, c)$ with $a + b + c = S$ and target $(a', b', c')$ also summing to $S$, we can route stones along chains, e.g. transfer from pile $i$ to pile $j$ along a sequence of single-stone moves.

Hence two configurations are mutually reachable iff their sums are equal. $\blacksquare$

Problem. A knight starts on an empty $8 \times 8$ chessboard at $(1,1)$. Each move it goes to a standard knight-move square. Prove: from $(1,1)$ the knight can reach $(8,8)$ in some sequence of moves.

Note. Unlike the bishop (which preserves square colour), the knight changes colour every move! A knight move changes one coordinate by 1 and the other by 2 — odd total = odd parity change.

Observe — invariant: colour mod 2 alternates

Each knight move changes the colour of the square (white ↔ black). Hence after $k$ moves, colour has parity $k \pmod 2$. $(1,1)$ is one colour; $(8,8)$ is the same colour (since $1+1 = 2$ and $8+8 = 16$ same parity). So we need an even number of moves.

Construction

Use a known knight's tour or explicit sequence: $(1,1) \to (2,3) \to (4,4) \to \cdots \to (8,8)$ (e.g. an 8-move path). $\blacksquare$

Problem. Three bottles initially contain $1, 4, 7$ stones. Operation: pick two bottles; transfer 3 stones from one to the other (must have at least 3 in the source). Can we reach $4, 4, 4$?

Observe

• Total = $1 + 4 + 7 = 12$ is invariant.
• Target total = $4 + 4 + 4 = 12$ ✓.
• Each count mod 3 is invariant! Because each transfer is $\pm 3$.
• Start: $(1, 4, 7) \equiv (1, 1, 1) \pmod 3$.
• Target: $(4, 4, 4) \equiv (1, 1, 1) \pmod 3$. ✓

Proof

Total stones and each bottle's count mod 3 are invariant. Both start and target match: total 12, each $\equiv 1 \pmod 3$. So reachable.

Construction. Move 3 from bottle 3 to bottle 1: $(4, 4, 4)$. Done in 1 step. $\blacksquare$

Problem. A $4 \times 4$ grid of integers; initially the cell at $(1,1)$ holds $1$, all others $0$. Operation: pick any $2 \times 2$ subgrid; add $1$ to two diagonally opposite cells and subtract $1$ from the other two. Can we reach the configuration with all zeros except $(4,4)$ holding $1$?

Observe — two invariants together

Compute the operation's effect on three candidate sums:

1. Total sum $S$: $\Delta S = +1 + 1 - 1 - 1 = 0$. Invariant.
2. Chessboard-weighted sum $C = \sum (-1)^{i+j} x_{ij}$: the four cells of a $2\times 2$ have signs $+, -, -, +$ (or similar). The two cells receiving $+1$ have opposite signs from those receiving $-1$; net effect depends on choice of diagonal.
3. Row-sum mod 2: each $2\times 2$ touches exactly 2 rows; in each affected row, two cells change, net change 0 in that row's sum. Hence each row sum is invariant.

Proof

Row sum invariance: each row's sum is invariant.

Start: row 1 sum = 1, all other rows = 0.

Target: row 4 sum = 1, all other rows = 0.

The two row-sum profiles differ. Hence target is unreachable. $\blacksquare$

Below is a curated catalogue of the most common invariants seen at AIMO / AMO / IMO level. Memorise the trigger conditions — when you see the operation type, the invariant should jump out.

1. Sum-Parity Invariant

2. Two-Colouring (Bipartite) Invariant

3. Modular Sum Invariant (mod $n$)

4. Weighted-Sum Invariant

5. Parity of Permutation Invariant

6. Count of a Special Feature Invariant

Invariants are powerful for impossibility proofs but are not always the right tool. Use this decision tree:

P6 — Three-Colour Tromino

Can a $9\times 9$ board with the centre square removed be tiled by L-trominoes (each covering 3 cells)? Hint: use a 3-colouring.

P7 — Power-of-Two Operation

Numbers $1, 2, 4, 8, \ldots, 2^{10}$ are on the board. Operation: pick two numbers $a, b$; erase both; write $a + b$. After 10 operations, one number remains. Find it.

P8 — Coin Stacking

Five stacks of coins have heights $1, 2, 3, 4, 5$. Operation: choose two stacks; transfer one coin from one to the other. Can we reach the configuration $0, 0, 0, 0, 15$?

P9 — Tree Labelling

Label the 7 vertices of a tree with integers. Operation: pick an edge; add 1 to one endpoint, subtract 1 from the other. Show: the set of reachable labellings is determined entirely by the sum of all labels.

P10 — Grasshopper Race

A grasshopper sits at $0$. Each second it jumps either $+1$ or $-1$. After 100 seconds, can it be at position $50$? Position $51$?

Pos 50:

Pos 51:

When you face a brand-new problem and don't immediately see an invariant, run through this systematic checklist:

1. Try simple sums. Total, mod 2, mod 3, mod $n$ for small $n$.
2. Try colourings. 2-colour (chessboard), 3-colour (diagonal stripes), 4-colour (2×2 blocks).
3. Try positional weighted sums. $\sum_i i \cdot x_i$, $\sum_i (-1)^i x_i$, $\sum_i \omega^i x_i$ with $\omega$ a root of unity.
4. Track signs / permutation parity. Count inversions, swaps, sign flips.
5. Compute the operation's effect symbolically. Write $\Delta Q$ for each operation; solve for $Q$ making $\Delta Q = 0$.
6. Look for hidden structure. Sometimes the invariant is a clever combination like $\sum x_i^2 \pmod 4$ or $\prod (1 + x_i)$.

Worked example — discovery process

Problem. On a $3\times 3$ board with numbers, operation: add 1 to all cells in a row or column. Can the configuration of all $0$s except a $1$ in the centre be reached from all $0$s?

Discovery.

1. Total sum changes by 3 each operation → sum mod 3 invariant. Start = 0; target = 1. $0 \neq 1 \pmod 3$. Unreachable.
2. Alternative invariant: row sums mod 3 — each column-operation changes them all by 1; each row-operation changes only one row sum by 3 (i.e. 0 mod 3). Quite involved.

The first invariant (total mod 3) suffices; no need for the more complex one.

Bonus problem. A circular arrangement of 7 integers initially reads $1, 0, 0, 0, 0, 0, 0$ (around the circle). Operation: choose two adjacent cells; add 1 to one, subtract 1 from the other. Can we reach $0, 1, 0, 0, 0, 0, 0$? Can we reach $1, 1, -1, 0, 0, 0, 0$?

Enter 1 (reachable) or 0 (not):

Config A ($0,1,0,0,0,0,0$):

Config B ($1,1,-1,0,0,0,0$):

We claimed that the position-weighted sum $T = \sum_c \text{pos}(c) \pmod n$ is invariant for chip-firing on an $n$-cycle. Let us derive this rigorously from scratch.

Setup

Vertices $V = \{0, 1, \ldots, n-1\}$ on a cycle. State $S$ assigns a non-negative integer $S(v)$ (number of chips) to each vertex. The total chip count is $N = \sum_v S(v)$.

Operation: at vertex $v$ with $S(v) \ge 2$, remove 2 chips from $v$; add 1 chip to vertex $v-1 \pmod n$ and 1 chip to vertex $v+1 \pmod n$.

Candidate invariant

Define $T(S) = \sum_v v \cdot S(v) \pmod n$. (Note: $v \cdot S(v)$ is computed in integers; the final result is reduced mod $n$.)

Calculation of $\Delta T$

Firing at $v$ changes $S$ as follows:

• $S(v) \to S(v) - 2$ → contribution to $T$: $-2v$.
• $S(v-1) \to S(v-1) + 1$ → contribution to $T$: $+(v-1)$.
• $S(v+1) \to S(v+1) + 1$ → contribution to $T$: $+(v+1)$.

Total: $\Delta T = -2v + (v-1) + (v+1) = -2v + 2v = 0$.

Hence $T$ is exactly invariant (not just mod $n$). $\square$

Generalisation

The same proof works for any weighting $w: V \to \mathbb{Z}$ satisfying the local condition $w(v-1) + w(v+1) = 2 w(v)$ for every $v$. This says $w$ is an arithmetic progression on the cycle — but on a cycle, the only such functions are constants. So $w = $ identity (treating $v$ as a number) is essentially the unique non-trivial weight, and it works mod $n$.

Higher-order invariants?

One can also check $T_2 = \sum_v v^2 \cdot S(v) \pmod{?}$. After firing at $v$: $$ \Delta T_2 = -2 v^2 + (v-1)^2 + (v+1)^2 = -2v^2 + (v^2 - 2v + 1) + (v^2 + 2v + 1) = 2. $$ So $T_2$ changes by exactly $+2$ per firing — it's a semi-invariant: a quantity with a known deterministic change. This means $T_2 - 2k$ (where $k$ = number of firings) is invariant.

This is one of the most beautiful invariant arguments in combinatorial mathematics. Although it goes beyond AIMO level, the technique is essential for high-end olympiad work.

Setup

Infinite half-plane $y \le 0$ filled with soldiers (one per integer lattice point). Operation: jump one soldier over an adjacent one (horizontally or vertically) into an empty cell; the jumped-over soldier is removed. Goal: get a soldier to $y = 5$.

The invariant

Place a weight $w(x, y) = \phi^{|x| + (5 - y)}$ at each lattice point $(x, y)$, where $\phi = \frac{\sqrt{5} - 1}{2} \approx 0.618$ is the inverse golden ratio (satisfying $\phi^2 + \phi = 1$).

Why it works

Define total weight $W = \sum_{\text{soldier positions}} w(x,y)$. A jump from position $P_1$ over $P_2$ to $P_3$ removes weights $w(P_1) + w(P_2)$ and adds $w(P_3)$. The choice of $\phi$ makes $$ w(P_3) \le w(P_1) + w(P_2) $$ for every legal jump (this requires casework, but the choice $\phi^2 = 1 - \phi$ exactly enables it).

So $W$ is a non-increasing quantity (a monovariant — preview of Part 2).

The bound

The total weight of all soldiers in $y \le 0$ is finite: $W_0 = \sum_{x \in \mathbb{Z}} \sum_{y \le 0} \phi^{|x| + 5 - y}$. This computes to a specific value $< 1$.

But to place a soldier at $(0, 5)$, we'd need $W \ge \phi^{0 + 0} = 1$. Since $W \le W_0 < 1$, we cannot reach $y = 5$. $\blacksquare$

The 15-puzzle is a $4 \times 4$ grid with 15 numbered tiles and one blank. A move slides a tile into the blank.

Invariant

Define the signature: $\sigma = (\text{parity of permutation of tiles}) + (\text{Manhattan distance of blank from corner}) \pmod 2$.

Why invariant

Each move transposes the blank with a neighbouring tile — an odd permutation (sign flip). Each move also changes blank's Manhattan-distance-to-corner by exactly 1 (odd). So both summands flip per move; their sum mod 2 is invariant.

Consequence

Half of the $16!/2 = 10^{13}$ configurations are reachable from the identity; the other half are not. A famous unreachable example: identity with tiles 14 and 15 swapped — the so-called "Sam Loyd 14-15 puzzle".

If one invariant fails to distinguish start from target, you need to find more. Here is a worked illustration.

Problem

$8$ pebbles arranged on a circle, alternately black and white: $B W B W B W B W$. Operation: pick a pebble; if it has the same colour as both neighbours, flip it. Can we reach all black?

Try invariant 1: count mod 2

Initially 4 black, 4 white. Target: 8 black, 0 white. Counts differ — but the operation flips one pebble, changing both counts by $\pm 1$. Hence "count of black mod 2" changes by 1 per move. Not invariant.

Try invariant 2: number of "monochromatic triples"

A monochromatic triple is three consecutive pebbles of the same colour. Initially: 0. The operation requires that the chosen pebble has same colour as both neighbours — i.e., a monochromatic triple already exists. Since initially there are zero, no operation is even legal.

Hence the configuration is frozen at the start; we cannot reach all-black. $\blacksquare$

For each problem, identify the invariant type in 30 seconds. Then attempt the proof.

1. Confusing necessary and sufficient. An invariant proves unreachability (if values differ). It does NOT prove reachability — that needs a construction.
2. Forgetting to check ALL operations. If the problem has multiple operation types, the invariant must be preserved by each one. Check each separately.
3. Wrong modulus. Picking mod 2 when you should pick mod 3, or vice versa. Try several until one works.
4. Sign errors in weights. When using weighted sums, double-check signs and arithmetic. A sign flip can hide an invariant.
5. Ignoring boundary cases. In domino tilings, edge cells may behave differently; make sure your invariant applies everywhere.
6. Not stating the invariant explicitly. Your proof must contain a sentence: "Define $Q = \ldots$. We claim $Q$ is invariant." Without this, examiners deduct heavily.
7. Conflating "is preserved" with "is constant". "Preserved" means $\Delta Q = 0$ per operation, hence constant along trajectories. Different starting states can have different $Q$ values.

The mutilated chessboard problem was first posed by philosopher Max Black in 1946 in his book Critical Thinking. It became famous as a textbook example of why "brute force search" is hopeless: there are roughly $10^{12}$ possible domino placements on the 62-cell board, yet a one-line colouring argument settles the question.

The problem also appeared in Solomon Golomb's classic 1965 monograph Polyominoes, which popularised tile-covering problems among mathematicians and computer scientists. Today the proof is a standard introduction to combinatorial invariants in undergraduate discrete-mathematics courses worldwide.

John Conway, the British mathematician famous for the Game of Life, posed the soldiers problem around 1961. He proved that no army of pieces can reach the fifth row of the upper half-plane, using the golden-ratio weighting we discussed in Deep 2.

The proof is widely regarded as one of the most elegant combinatorial arguments ever discovered. It demonstrates the deep principle that the right choice of weight can convert a discrete combinatorial impossibility into a continuous inequality.

Decades later, the problem was extended to higher dimensions and continuous variants — leading to current research in chip-firing theory, tropical geometry, and combinatorial game theory.

In 1880, the American puzzle inventor Sam Loyd offered a $1,000 prize to anyone who could swap the 14 and 15 tiles in the standard 15-puzzle. (The prize would be roughly $30,000 in 2026 dollars.)

The prize was never paid. The reason: the swap of two adjacent tiles is an odd permutation, while every legal move corresponds to a transposition of the blank — an odd permutation too. Each move changes the blank's position, and to return the blank to its starting square requires an even number of moves. Even number of odd permutations = even permutation overall. A single transposition of 14 and 15 is odd. Contradiction.

This was one of the first publicised uses of the parity-of-permutation invariant outside pure mathematics. Today the same idea underlies the analysis of Rubik's cube reachability, sorting networks, and quantum gate decomposition.

The abstract chip-firing game was formalised by Anders Björner, László Lovász, and Peter Shor in 1991. They showed that chip-firing on any finite graph has a remarkable property: regardless of which vertex you fire first, the process either continues forever or terminates in a unique stable configuration that depends only on the starting state.

This abelian property is itself a higher-order invariant: the final configuration is invariant under the choice of firing order.

Today chip-firing connects to: divisor theory on algebraic curves (the Baker-Norine theorem, 2007), abelian sandpile groups, the matrix-tree theorem, and tropical Jacobians. It is an unusually deep example of how a simple invariant idea opens onto modern algebraic geometry.

Day-by-day schedule

Continuation

After Part 1 (this file), proceed to Part 2 (Extremal Principle & Monovariants), then Part 3 (Combined Proof Synthesis). Together these three parts form the complete W15 Proof II curriculum.