Invariants
An invariant is a quantity that never changes, however the moves in a puzzle are made: the parity of a sum, a total, a product, or a colouring count. If the start and the target have different values of the invariant, the target can never be reached, and no amount of trying will get there.
A monovariant is a quantity that only ever moves one way (it always increases, say). It proves that a process must stop.
When to try it
- The problem describes repeated moves and asks whether a position can ever be reached.
- Many choices are possible at each step, so trying them all is hopeless.
- Something about the position looks ‘protected’: the total of the numbers, the number of heads modulo 2, the colours of the squares covered.
Watch out: An invariant can prove that something is impossible, but never that it is possible. For that you need an explicit sequence of moves.
Worked example
The numbers 1 to 10 are written on a board. Again and again, two numbers are rubbed out and replaced by their difference (the larger minus the smaller). In the end one number is left. Can it be 0?
Show the solution
- Look for something that never changes. Replacing a and b by a − b changes the total by 2b, an even number.
- So the total stays odd or even for ever. At the start it is 1 + 2 + … + 10 = 55, which is odd.
- The last number is the total at the end, so it is odd.
Answer: No: the last number is always odd
Practise: 38 problems that use invariants
Other strategies
Organised cases · Count the opposite · Working backwards · Extremal principle · Pigeonhole principle · Parity and remainders · Symmetry · Spot the pattern and generalise · Proof techniques