Invariants and Monovariants

Why This Matters

Many olympiad problems describe a process: a game, a configuration, a move-by-move transformation: and ask whether some target state is reachable, or whether the process terminates. The two go-to techniques:

Invariant: a quantity preserved by every allowed move. If start and target have different invariant values, the target is unreachable.
Monovariant (a.k.a. potential function, Lyapunov function): a quantity that strictly decreases (or strictly increases) with each move. If the quantity is bounded below (above), the process must terminate.

The combination handles both configuration questions ("can we reach state $T$ from state $S$ ?") via invariants and termination questions ("does the process always halt?") via monovariants. The technique generalizes far beyond olympiads: loop-termination proofs in software verification, Markov-chain mixing arguments, simulated annealing, and reinforcement learning all use the same pattern.

The Setup

A process has:

A state space $\mathcal{S}$ .
A set of moves (operations) $M \subseteq \mathcal{S} \times \mathcal{S}$ .
A start state $s_0$ and (often) a target state $s_T$ or a halting condition.

Invariant. A function $I: \mathcal{S} \to X$ is an invariant if $I(s) = I(s')$ for every move $(s, s') \in M$ .

Monovariant. A function $\phi: \mathcal{S} \to \mathbb{R}$ is a monovariant if $\phi(s) > \phi(s')$ for every move (i.e., strictly decreasing), or symmetrically, strictly increasing. We say $\phi$ is strict on $M$ .

Conclusions.

Invariant $\Rightarrow$ $I(s_0) = I(s)$ for every reachable $s$ . So if $I(s_0) \ne I(s_T)$ , $s_T$ is unreachable.
Monovariant (strict) on a well-ordered $X$ $\Rightarrow$ the process must halt. The number of moves is bounded by $|\phi(s_0) - \phi_{\min}|$ in the discrete case.

Worked Example: The 15-Puzzle Parity Invariant

Example

The 15-puzzle (Sam Loyd, 1880)

Problem. The 15-puzzle has tiles numbered 1-15 in a 4x4 grid with one empty cell. A move slides a tile into the empty cell. Show that no sequence of moves can swap tiles 14 and 15 while leaving all other tiles in their starting positions.

Solution. The state is a permutation $\sigma$ of $\{1, \ldots, 15\}$ plus the position of the empty cell $(r, c) \in \{1, 2, 3, 4\}^2$ . Define the invariant:

$I(\sigma, r, c) = \text{sign}(\sigma) \cdot (-1)^{r + c} \in \{+1, -1\}.$

Check. Each move slides one tile, swapping it with the empty cell. The permutation $\sigma$ gets a single transposition (sign flip), and the empty cell's $(r + c)$ parity also flips. So both factors flip, and $I$ is preserved.

Apply. In the start state, $\sigma = \text{id}$ has sign $+1$ , and the empty cell is at $(4, 4)$ giving $(-1)^{4+4} = +1$ , so $I = +1$ .

The target state has $\sigma = (14, 15)$ a transposition with sign $-1$ , and the empty cell back at $(4, 4)$ giving $(-1)^8 = +1$ , so $I = -1$ .

Different invariant values: target unreachable.

This argument was first made precise by Johnson (1879) and Story (1879), independently of the toy: it underlies the classification of solvable / unsolvable configurations.

The 15-puzzle parity argument is the canonical illustration: the invariant is not obvious (you have to think to see that empty-cell parity must couple with permutation sign), but once chosen, the proof is one line.

Worked Example: The Chocolate-Bar Problem

Example

The chocolate-bar problem

Problem. A chocolate bar is a 6x8 grid of squares. Two players alternate breaking the bar along grid lines (the broken pieces stay in play). The player who cannot move loses. (Each move strictly increases the number of pieces.) Show that the game terminates; if both play perfectly, who wins?

Solution: termination via monovariant. Every move turns one piece into two pieces. Let $\phi(s) = 6 \cdot 8 - \#\text{pieces}(s)$ . At the start, $\phi = 48 - 1 = 47$ ; the game ends when $\phi = 0$ (every piece is a single square). Each move decreases $\phi$ by 1. So the game lasts exactly 47 moves.

Solution: who wins. Since the game lasts an odd number of moves and the first player makes odd-numbered moves, the first player makes the 47th move; the second player has no move and loses. So the first player always wins.

The cleanness. The monovariant $\phi$ doesn't depend on which moves are chosen: it just counts pieces. This makes the analysis trivial and game-theory-free.

This is the invariant counting technique: count something that changes deterministically per move, regardless of strategy.

Choosing the Invariant or Monovariant

The hard part is finding the right quantity. Useful heuristics:

Cue	Try as invariant/monovariant
Game with allowed swaps	Sign of permutation, parity of inversions
Game on a grid with reflection moves	Parity of $r + c$ for moved cell
Sum / product / coloring constraint	Sum modulo $k$ for some $k$
Numbers replaced by combinations	Sum, max, min, GCD, LCM
Configuration of points	Centroid, diameter, total distance
Process with shrinking pieces	Number of pieces, total area
Recursive / fractal structure	Multinomial / characteristic polynomial
Game tree	Sprague-Grundy number (advanced)

When in doubt, compute the candidate quantity on a few moves and see if it's preserved or strictly decreasing.

Worked Example: Numbers on a Blackboard

Example

Replacing numbers on a blackboard

Problem. The numbers $1, 2, \ldots, 100$ are written on a blackboard. In each move, you erase two numbers $a$ and $b$ and write $|a - b|$ in their place. After 99 moves, one number remains. What can it be?

Solution. The total parity: $a + b$ has the same parity as $|a - b|$ (since $a + b - |a - b| = 2 \min(a, b)$ is even). So the parity of the sum is invariant.

Initial sum: $1 + 2 + \cdots + 100 = 5050$ , which is even. So the final number must be even.

The final number can be 0 (if at some point $a = b$ are erased and the difference is 0), 2, 4, etc. Constructions exist for many even values. The question "what can it be?" asks for the range; the invariant pins down "even" but nothing more.

Note: the same problem appears in Engel and Larson with slight variations.

This is the invariant modulo 2 pattern: when moves combine two numbers via a function, often only the parity of some statistic survives.

Termination via Monovariants

For termination, the monovariant must be:

Real-valued (or take values in a well-ordered set).
Bounded below (or above) by some fixed constant.
Strictly decreasing (or increasing) per move.

Then by well-ordering on $\mathbb{N}$ or by the completeness of $\mathbb{R}$ (with a discrete-step hypothesis), the process halts.

A classical example: bubble sort terminates because the number of inversions is a monovariant: each swap decreases it by 1, and it's bounded below by 0. The number of moves equals the initial number of inversions.

In ML, gradient descent on a $\mu$ -strongly convex function has $f(x_k)$ as a monovariant (modulo the step-size constant) and converges by exactly this argument.

Common Mistakes

Watch Out

Confusing 'invariant' and 'monovariant'

Invariant: preserved by every move. Used to prove non-reachability. Monovariant: strictly changes per move. Used to prove termination. Mixing them up gives wrong proofs.

Watch Out

Strictness of monovariants

A monovariant must change strictly on every move. If some moves leave it constant, you have an invariant on the restricted move set, but termination is no longer guaranteed on its own: you need a secondary monovariant for the unchanged-quantity moves.

Watch Out

Non-bounded monovariants don't give termination

$\phi(s_k) = \phi(s_0) - k$ is monotone but unbounded below on $\mathbb{R}$ . For termination, you need $\phi$ bounded below on the state space. In olympiad problems, this is usually $\phi: \mathcal{S} \to \mathbb{N}$ , where well-ordering forces termination.

Watch Out

Forgetting non-uniqueness

Multiple invariants can hold at once; finding one is enough to prove unreachability. A finer-grained invariant gives a sharper non-reachability claim. The 15-puzzle invariant splits states into two equivalence classes; finer invariants might split into more, but for the 14-15 swap problem, parity suffices.

Exercises

ExerciseCore

Problem

Five 1's and five 2's are written in a row. In each move, you erase two adjacent identical numbers and replace them with one. (E.g., $1, 1 \to 1$ or $2, 2 \to 2$ .) Can the row end with one of each (1, 2)?

ExerciseAdvanced

Problem

On a 9x9 grid, we place pieces such that each row and column contains an even number of pieces. Show that the total number of pieces is even.

ML and Production Connections

Loop termination in formal verification. Proving a loop terminates often uses a ranking function — monovariant: that maps the state space into a well-ordered set. Coq's Function keyword and Isabelle's function command require an explicit ranking function.
Lyapunov functions in control theory. The Lyapunov function for a dynamical system $\dot{x} = f(x)$ is exactly a monovariant on a continuous state space. Used in reinforcement learning for stability analysis (Berkenkamp et al. 2017).
Convergence proofs in optimization. Gradient descent on convex $f$ : the objective $f(x_k)$ is a monovariant. In stochastic settings, $\mathbb{E}[f(x_k)]$ is the monovariant.
Markov chain mixing and detailed balance. The KL divergence to stationary distribution is a monovariant (the H-theorem). Used in MCMC convergence analysis.

Cross-Network Links

ProofsPath: extremal-principle is the natural complement (consider the smallest / largest / extremal example); well-ordering-principle underwrites monovariant-based termination; proof-by-infinite-descent is a special case of monovariant on $\mathbb{N}$ .
TheoremPath: stochastic-gradient-descent-convergence uses monovariants in the optimization context.

References

See structured references block. Primary entry points: Engel Ch 2 for the technique treatment; Larson Ch 4 for worked examples; Johnson and Story (1879) for the original 15-puzzle analysis; Aigner-Ziegler for elegant invariant proofs across mathematics.