Technique Encyclopedia

Invariants

What it is

An invariant is some property of a system — a sum, a parity, a gcd, a coloring — that stays exactly the same no matter which allowed move is applied. If a claimed final state doesn't match the invariant's required value, reaching that state is provably impossible, with no need to search through every possible sequence of moves.

Signals that suggest using it

A process repeatedly transforms a configuration via some fixed set of allowed moves.
The problem asks whether a specific final state can ever be reached.
"Show that ... is impossible" or "prove that ... always holds, no matter the sequence of moves."

When it's effective

Invariants are the fastest route to an impossibility proof — one clean argument rules out every possible sequence of moves at once, without needing to consider any of them individually.

When it's not effective

If every reachable state actually is achievable (nothing is truly ruled out), hunting for an invariant wastes time — there's nothing to find, and a direct construction of the target state is what's needed instead.

Simple example

Problem

A board shows the pair (3, 5). Each move replaces (a, b) with either (a+b, b) or (a, a+b). Can the pair (5, 5) ever appear?

Solution

gcd(a,b) is unchanged by either move, since gcd(a+b,b)=gcd(a,b). The starting gcd is gcd(3,5)=1, but gcd(5,5)=5 — since 1 ≠ 5, (5, 5) can never appear.

AMC-style example

Problem

The numbers 1 through 10 are written on a board. In each move, two numbers a and b are erased and replaced with a+b-1. After 9 moves, one number remains. What is it?

Solution

Each move changes the sum of all numbers on the board by exactly (a+b-1)-(a+b)=-1 — so the sum decreases by exactly 1 every move, regardless of which numbers are chosen. Starting sum: 1 + 2 + ... + 10 = 55. After 9 moves, the sum has dropped by 9, so the final number is 55-9=46.

Monovariants Parity Testing Small Cases