Invariant Method

Intro to Proofs · Axiom Academy

Find a quantity the rules can never change — then any state where it has the wrong value is provably out of reach. Start with an invariant equal to I , run any sequence of allowed moves, and it is still I at the end. Watch three tiles whose values are . The only allowed move is a transfer : take some amount from one tile and add the same amount to another. Each move rewrites the individual numbers, yet the sum S = 3 + 5 + 7 = 15 never budges. 2. Classic Example: The Mutilated Chessboard Can you tile a chessboard with two opposite corners removed using dominoes? A standard chessboard has 64 squares. Remove two opposite corners, leaving 62 . Each domino covers exactly 2 squares, so 31 dominoes would cover 62 — the count works out. It looks possible. It is not. The invariant: every domino, however you lay it, covers exactly one black square and one white square. So any tiling covers equal numbers of black and white. But two opposite corners are the same colour, so removing them leaves 30 of that colour and 32 of the other. With the colours unbalanced, no set of dominoes can ever cover the board. 3. Monovariants: One-Way Change Monovariants are built for proving termination . If a quantity must strictly decrease at each step and is bounded below — for instance, it stays a non-negative integer — then it cannot decrease forever, so the process must eventually stop. The remainder strictly decreases at each step, so is reached in finitely many steps.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.