Invariants and Monovariants: Proving That Something Is Impossible
When a problem asks whether a configuration can ever be reached, stop simulating and start looking for a quantity that never changes — or always changes the same way.
Olympiad Desk · Core Learning
What you will take away
- An invariant is preserved by every legal move; a monovariant always moves one way
- Parity and colouring produce invariants out of thin air
- A bounded monovariant proves a process must stop
- The correct quantity is usually suggested by the moves, not by the target
Simulating a process is a trap: olympiad processes run for enormous numbers of steps. The escape route is to find a number, colouring or sign that behaves predictably under every legal move.
Invariant: the quantity that refuses to move
If every legal move keeps some quantity Q constant, then anything reachable from the start has the same Q as the start. Compute Q for the start and the proposed end; if they differ, the end is unreachable. Parity of a sum, the sum of all numbers modulo 2, a colouring count on a board — these are the usual candidates.
Monovariant: the quantity that always moves one way
If a positive integer quantity strictly decreases with every move, the process cannot run forever. This is the standard way to prove that a game terminates, and it doubles as a proof that pieces cannot be shuffled indefinitely.
Worked problems
- 1
Numbers 1 to 100 are written on a board. You repeatedly erase two numbers and write their sum. Prove the final number does not depend on the order of operations.
Show hint
Which quantity is untouched by the operation "replace a and b with a + b"?
Show solution
The sum of all numbers on the board is preserved: removing a and b removes a + b but immediately adds a + b back. Each step reduces the count by one, so after 99 steps the board holds exactly the total sum, independent of the pairing chosen.
Answer: The final number is 1 + 2 + … + 100 = 5050.
- 2
A knight starts on a corner square of a standard chessboard. Prove that it can never return to that square after exactly 63 moves.
Show hint
The knight alternates colour on every move; count how many moves of each type a return to the start requires.
Show solution
A knight changes square colour on every move, so after an even number of moves it is on the same colour as the start. 63 is odd, and a corner square is a single fixed colour, so after 63 moves the knight sits on the opposite colour and cannot be back on the starting square.
Answer: Parity of colour makes an odd-length return impossible.
