When to use an invariant in a competition problem

Nothing in a competition problem ever says "invariant". What the problem says is that chips jump, numbers get erased and rewritten, lockers get toggled, tokens all step at once, and then it asks you to prove something is impossible. Students who know perfectly well what an invariant is still spend twenty minutes pushing the process around, because the statement gave them a verb and they obeyed it.

The recognition move is to stop playing the game and ask what the game cannot touch. This guide is about when that instinct is the right one, which candidate to test first, and the thirty-second test that settles it. The definition itself lives on the invariants page and is not repeated here.

The four signals

• A process with legal moves. "Repeatedly", "at each step", "a move consists of". The moment a problem defines an operation and lets you iterate it, invariants belong on your shortlist before you have even read the question.
• The question is "prove you can never". Impossibility is what an invariant is for. There are infinitely many move sequences and you are being asked about all of them at once, so no amount of playing will finish the proof. A quantity every move preserves settles them all in one line.
• A final state the problem swears is unique. "Show the last number does not depend on the order of the moves", or simply "find the final value" when the order is clearly free. If the order may vary and the answer may not, the answer is an invariant, and computing it is the entire solution.
• A tiling, covering, or everybody-moves-at-once question. Dominoes on a mutilated board, tokens each stepping to a neighbour. Here the invariant almost always wears paint: it is a colour count.

The ladder of candidates

You do not invent an invariant from nothing. You test candidates in a fixed order, and one of them survives. Work down this ladder:

1. The sum of the numbers on the board.
2. The sum modulo something small: 2 first, then 3, then whatever modulus the problem's own numbers keep hinting at.
3. A product, and in particular a product of shifted terms like $(1+x)$ over every entry.
4. A count modulo 2: how many odd entries, how many minus signs, how many chips on dark squares.
5. A colouring of the board, weighted if two colours are not enough.
6. A position sum: label the cells $0, 1, \dots, n-1$ and add up where the pieces sit, modulo something.

Most invariants you will meet before olympiad level sit on the first three rungs. If all six die, the move was designed around a feature you have not named yet (position, parity of position, residue, colour), and you should go looking for that feature rather than for a formula.

The one-move test

Whatever the candidate, the test is identical and takes half a minute. Take a general state, apply one legal move, and compute the candidate before and after. Three outcomes:

• Unchanged. You have an invariant. Now compare the starting value with the value the target demands.
• Changed by the same fixed amount every time. You have a drift, which is just as good: subtract the step count and the difference is invariant.
• Changed unpredictably. Next rung.

The word doing the work is general. Testing your candidate on one convenient move is the most common way this goes wrong, because convenient moves are exactly the ones that preserve things by accident.

Two boards, one move apart

Write $1, 2, \dots, 6$ on a board. A move erases two numbers $a, b$ and writes $|a-b|$. The sum is not preserved, but it drops by $2\min(a,b)$, so its parity is. The starting sum is $21$, odd, and every legal move keeps it odd, so the single number left at the end is odd, and can never be $0$. Note what is not true: the final value itself is not determined, and different orders really do leave different numbers. Only the parity is nailed down, and for an impossibility proof that is plenty.

Now change one symbol. Same board, but a move writes $a+b+ab$. The sum changes, the product changes, and the second rung of the ladder gives nothing. Test the product of $(1+x)$ over all entries: $(1+a)(1+b) = 1 + a + b + ab$, which is exactly $1$ plus the number that replaced them. So that product never changes. It starts at $2 \cdot 3 \cdots 7 = 5040$, and the last number standing is forced to be $5039$, whatever order you use. Here the invariant does not prove an impossibility at all: it computes the answer.

When the invariant is a colour

Take the mutilated chessboard: delete two opposite corners and try to cover the remaining 62 squares with 31 dominoes. Plain counting is silent, since $62 = 2 \times 31$ exactly. Paint the board in the usual alternating pattern and the obstruction is immediate. Every domino, wherever it lands, takes one square of each colour, while the two deleted corners were the same colour as each other, leaving 32 of one and 30 of the other. The check attached to this guide does not take that on trust: it counts tilings by dynamic programming, finding 12,988,816 of the intact board and none at all of the cut one.

The same paint, a different conclusion, in a 5×5 grid where every token steps to an orthogonally adjacent square at once. A step always flips colour, and 25 cells split 13 to 12, so the 13 tokens on the majority colour would all have to land on 12 cells. The colouring page treats this as a technique of its own, which is fair, but the two are the same idea: a colour count is an invariant that someone has painted onto the board.

Signal three shows up in the 100 lockers, toggled by student $k$ at every $k$-th door. Nobody tells you the students' order is irrelevant, but the question presumes it, and that presumption is the tell: each locker's fate depends only on the parity of how many divisors its number has, which no reordering can change.

Where an invariant will not help you

An invariant proves impossibility. It very rarely proves possibility, and treating it as though it does is where marks disappear. If the start and the target agree on every invariant you can find, you have learned only that the obvious obstruction is absent. You still owe a construction, and the construction is separate work. "The parity matches, therefore it can be done" is not an argument.

The other trap is stopping too early. If the sum survives your test, that does not make it the right invariant: it makes it a true statement that may be useless. Ask what the target state needs, and keep climbing the ladder until you find a quantity on which the start and the goal actually disagree.

What to do with this

Recognition trains on volume, not on reading. Take ten problems that describe a process, and for each write two lines only: the move, and the first candidate that survives one application of it. Do not solve them. You will get through ten in the time one full write-up takes, and pattern-matching is the thing you are actually short of.

Lemma teaches this as a named technique rather than a trick you happen to meet twice: the invariants page has the statement and the monovariant sibling, the problem archive carries the process problems above in full with difficulty and expected time, and the daily problem posts a fresh one every day in three tiers with no account needed. The companion piece on how to spot a pigeonhole problem does the same job for the other technique that hides behind ordinary-looking words.