Invariants and Monovariants

A whole family of interview puzzles asks whether you can get from one arrangement to another using some set of moves. Left to yourself you will shuffle the pieces for five minutes, fail, and be unable to say whether you failed because it is impossible or because you were unlucky. The way out is to stop looking at the arrangement and start looking for a number attached to it that the moves treat predictably.

• An invariant is a quantity that every legal move leaves untouched. If the start and the target disagree on it, no sequence of moves can connect them. That is an impossibility proof, and usually a one-liner.
• A monovariant is a quantity that every legal move pushes strictly in one direction, and which cannot run past some bound. That proves the process must stop, and often tells you where.

Worked example: the chameleons

An island has 13 red, 15 green and 17 blue chameleons — 45 in total. Whenever two chameleons of different colours meet, both change into the third colour. Can they all end up the same colour?

Try it for a minute before reading on. It is very tempting to believe some clever sequence works.

The move, in numbers. Say red and green meet. Red drops by 1, green drops by 1, blue rises by 2. Now look at those changes modulo 3: $-1 \equiv 2$ and $+2 \equiv 2$. Every single count changes by the same amount, $+2$ modulo 3, on every move, whichever two colours meet.

The invariant. Because all three counts shift by the same amount each time, the differences between them never change modulo 3. Equivalently: the three counts occupy three residue lanes modulo 3, and a move slides all three dots along together without ever letting them collide.

Check the start and the target. $13 \equiv 1$, $15 \equiv 0$, $17 \equiv 2$ modulo 3 — all three lanes occupied, one each. The target "all one colour" is a state like $(45, 0, 0)$, whose residues are $0, 0, 0$ — all three in the same lane. The lanes can never merge, so it is impossible. No search required.

Worked example: the bean jar (both tools at once)

A jar holds 7 white and 12 black beans, and beside it sits an unlimited pile of spare black beans. Repeat this step: pull out two beans at random. If they are the same colour, throw both away and drop in one spare black bean. If they are different colours, throw away the black one and put the white one back. What colour is the last bean?

First, does it even end? The monovariant: count the beans. Same colour — remove 2, add 1, net $-1$. Different colours — remove 2, return 1, net $-1$. Every step removes exactly one bean, and the count cannot go below one, so from 19 beans the process stops after exactly 18 steps with a single bean left. Termination proved, no case analysis.

Now, which colour? The invariant: track the whites. Two whites drawn — whites fall by 2. Two blacks drawn — whites unchanged. One of each — the black is discarded and the white returns, so whites unchanged. In every case the number of whites changes by 0 or $-2$, so its parity never changes. We started with 7 whites, an odd number, so the count of whites is odd at every moment, including at the end. One bean, odd number of whites: the last bean is white.

Notice how little work that was. The randomness in "pull out two at random" turned out to be irrelevant — the answer is forced regardless of the draws.

What to look for, and where else it works

The usual suspects for an invariant are parity (odd or even), a count modulo some small number, a colour balance on a board, a sum or product of labels, and the sign of a permutation. Monovariants are usually a size, a total distance, an energy, or a count of disorder — anything bounded below that each move strictly decreases.

The same two tools crack the mutilated chessboard (each domino covers one square of each colour, so a colour imbalance kills the tiling), the classic 15-puzzle (sliding tiles preserves the parity of the permutation, so the swapped-14-and-15 position is unreachable), Nim (the XOR of the pile sizes is zero exactly at losing positions, and every move away from zero can be answered by a move back to it), and sorting by adjacent swaps (the number of out-of-order pairs drops by one each swap, so the process must terminate).

The quant version of this habit is looking for conserved quantities in a model: a no-arbitrage relation that must hold whatever the price does, or a quantity that provably shrinks each iteration of an algorithm. Same instinct, bigger stakes.