Invariants & Monovariants

Find what a move can never change — and rule out entire futures at once.

The idea

An invariant is a quantity computed from the state of a process that no allowed move changes. It settles questions of reachability: every reachable state carries the starting value of the invariant, so any state carrying a different value is unreachable by every sequence of moves. This is the standard way to prove a state unreachable — failed attempts prove nothing, while one invariant rules out all move sequences at once.

A useful invariant is rarely a plain total. More often it is a parity, a remainder modulo a fixed number, or a difference of two counts — a quantity coarse enough to survive moves that change everything else.

A monovariant is a quantity that every move pushes in the same direction. It cannot rule a state out, but a whole-number monovariant that strictly decreases and cannot fall below a floor proves that the process terminates.

Reach for an invariant when the question is whether a state can be reached or what the final state must be, and for a monovariant when the question is whether the process ends.

Ways to work on it

• Walkthrough. Find quantities a game's moves never change, and one that only ever decreases.
• Practice. Decide whether a cup-flipping puzzle is solvable, using a parity invariant.
• Hardest. A color-switching puzzle: find the invariant that decides which endings are reachable.

Not sure where to start? Take the ten-question placement test.