Invariants and Monovariants

Invariant

A quantity unchanged by every allowed move. If the start and target differ in it, the target is unreachable — an impossibility proof in one line.

Monovariant

A quantity that only increases (or only decreases). Proves termination, and bounds the number of moves.

Together they answer the two questions constructive problems ask: is it possible? and how many moves?

Finding an invariant

Ask what each move preserves:

Move	Preserves
Swap two adjacent elements	parity of the permutation flips — so parity is invariant under pairs of swaps
Flip a cell and its neighbours	the sum mod 2 over a fixed subset
Move a token on a coloured board	the colour class (if moves preserve colour)
Add $k$ to two elements	the difference mod $k$; the total mod $2k$
Replace $a,b$ with $a+b$	the total sum; the gcd of everything
Replace $a,b$ with $|a-b|$	the gcd; parity of the sum
Rotate a 3×3 face	permutation parity + orientation sums (Rubik’s cube)
Reverse a subarray	the multiset; the number of inversions mod something

Candidates to test: sum, sum mod $k$, parity, XOR, gcd, a weighted sum $\sum w_i{a}_i$, the number of inversions, a colouring count, and the multiset of values.

Worked examples

The 15-puzzle

A move slides a tile into the blank. The invariant is

$(\text{permutation parity})+(\text{row distance of the blank from home})\mathrm{mod}2.$

Each move changes both by 1, so the sum is invariant. Exactly half of all configurations are reachable — which is why the classic “swap two tiles” puzzle is unsolvable.

Chessboard with two corners removed

Remove two opposite corners from an $8\times 8$ board and try to tile it with dominoes. Each domino covers one black and one white square; the removed corners share a colour, so the counts differ by 2. Impossible.

A colouring argument is an invariant argument.

Coins / chip-firing

Replacing $a$ and $b$ with $a+b$ preserves the total; replacing them with $\gcd$-preserving operations keeps $\gcd$ of the whole set invariant. So a target is reachable only if it is a multiple of that gcd — the same fact that underlies Bézout’s identity.

Sorting by adjacent swaps

The number of inversions decreases by exactly 1 per useful swap, so it is a monovariant: the process terminates in exactly $\mathrm{inv}$ moves, and that is the minimum.

Monovariants and termination

To prove a process terminates:

1. Find a non-negative integer quantity that strictly decreases each step.
2. It cannot decrease forever, so the process stops.
3. Its initial value bounds the number of steps.

Process	Monovariant
Bubble sort	inversions
Euclid’s algorithm	$\min (a,b)$
Chip-firing on a graph	a potential function
Local search	the objective value
Augmenting paths	remaining capacity / flow value
Simplex	the objective (with anti-cycling)
Tonelli-Shanks	the order of $t$ in the 2-Sylow subgroup

Using invariants constructively

Invariants prove impossibility. To prove possibility, show the invariant is the only obstruction:

1. Compute the invariant for the start and target — if they differ, output “impossible”.
2. If they agree, give an explicit construction reaching the target.

That two-part structure is the standard shape of a constructive problem’s solution, and step 2 is usually an induction: reduce to a smaller case, solve, extend.

The checklist for a constructive problem

1. Compute small cases by brute force. Which are solvable?
2. Look for a pattern in the solvable ones — that pattern is the invariant.
3. Verify the invariant is preserved by every move.
4. Construct a solution whenever the invariant permits, usually by induction.
5. Bound the number of moves with a monovariant if the problem asks.

Step 1 is not optional. A brute force over $n\le 6$ answers “which cases are possible” in seconds and makes the invariant visible.

See also: Parity Arguments · Small Cases · Proof Techniques