Invariants & Monovariants

Study Sheet

Invariants & Monovariants

Quantities that never change, or move one way

Process Problems

Concept
Invariant
Two opposite corners removed: 30 cells of their color remain against 32 of the other, and each domino covers one of each.

Find a quantity — a parity, a sum mod kk, a coloring — that a process never changes. If start and target differ in it, the target is unreachable.

In plain terms. Spot something that stays the same no matter what moves you make; if the goal has a different value, you can never get there.

Example. On a chessboard, a domino always covers one black and one white square, so you can never tile a board with two same-color corners removed.

Concept
Monovariant

A quantity that only increases (or only decreases) each step proves the process must terminate.

In plain terms. Find something that always moves one direction; since it can't do so forever, the process has to stop.

Example. If each move strictly lowers a positive whole-number "energy," the moves must eventually end.

Proof Ideas That Win

Concept
Invariants

An invariant is a quantity a process never changes. If the start and the goal have different invariant values, the goal is impossible.

In plain terms. Find something the moves cannot alter, then compare start to finish.

Example. A domino covers one black and one white square, so the count (black squares covered) −- (white squares covered) is invariant — which is why a board missing two same-colored corners cannot be tiled.

Tip
The pigeonhole principle

Placing more than nn objects into nn boxes forces some box to hold at least two.

In plain terms. Too many things, too few slots — a collision is guaranteed.

Example. Among any 1313 people, two share a birth month, because there are only 1212 months.

Concept
The extremal principle

Look at the largest, smallest, or closest element — its extremeness forces structure the middle elements do not have.

In plain terms. Start the argument at the most extreme case; it has the least room to misbehave.

Example. Among finitely many points not all on one line, a pair at minimum distance is the classic starting move for contradiction arguments.

Invariants and Monovariants Worked in Full

Tip
Two questions, two tools

Can the target be reached? Find a quantity that no move changes (a residue, a parity, a weighted count) and compare its value at the start and at the target. Must the process stop? Find a quantity that every move strictly decreases and that takes values in a set with no infinite decreasing sequence — nonnegative integers, or pairs of them ordered lexicographically.

An invariant proves impossibility and nothing else: equal values at start and target prove nothing about reachability. A monovariant proves termination only if it is bounded below AND moves in steps that cannot shrink forever; a positive integer that drops by at least 11 each time can drop at most its starting value times, which also bounds the number of moves. Finding either quantity is a matter of computing what one move does to the natural candidates — the sum, the sum of squares, counts mod small numbers — and keeping the one whose change has a sign or vanishes.

Example
Example 1: chameleons

An island has 1313 red, 1515 green and 1717 blue chameleons. When two of different colors meet, both change to the third color. Can all 4545 chameleons become the same color?

Step 1 — a meeting changes the counts (R,G,B)(R, G, B) by (−1,−1,+2)(-1, -1, +2) in some order. Each pairwise difference, such as R−GR - G, changes by 00 or ±3\pm3. So the differences mod 33 are invariant.

Step 2 — at the start, R−G=−2R - G = -2, G−B=−2G - B = -2, R−B=−4R - B = -4: none is divisible by 33.

Step 3 — if all were one color, the other two counts would be 00 and their difference 00, divisible by 33. Impossible. ■\blacksquare

How to find it. A move changes three counts by −1,−1,+2-1, -1, +2; the combinations that ignore such a move are differences mod 33. Compute the effect of one move on the obvious quantities and look for the one that does not change.

Example
Example 2: T-tetrominoes on a 10 × 10 board
Two T-tetrominoes on the checkered board: one covers one shaded cell and three plain ones, the other the reverse.

Can a 10×1010\times10 board be tiled by 2525 T-tetrominoes (four cells: three in a row and one attached to the middle)?

Step 1 — color the board like a chessboard: 5050 black and 5050 white cells.

Step 2 — a T-tetromino covers either 33 black and 11 white or 11 black and 33 white cells (its three-in-a-row alternate colors, and the attached cell has the color opposite the middle one).

Step 3 — if kk tiles are of the first kind and 25−k25 - k of the second, the black cells covered number 3k+(25−k)=25+2k3k + (25 - k) = 25 + 2k. This must be 5050, so 2k=252k = 25 — impossible for an integer kk. ■\blacksquare

How to find it. Each tile's color split is unbalanced, so an equal split overall needs the imbalances to cancel in pairs. Parity of the number of tiles then decides.

Example
Example 3: the pentagon game

Integers are written at the vertices of a regular pentagon, with positive sum. If three consecutive vertices carry x,y,zx, y, z with y<0y < 0, a move replaces them by x+yx + y, −y-y, z+yz + y. Prove that the game must end, whatever moves are chosen. (IMO 1986/3.)

Step 1 — the sum S=x1+⋯+x5S = x_1 + \cdots + x_5 is invariant: the move adds y−2y+y=0y - 2y + y = 0.

Step 2 — try f=∑i=15(xi−xi+2)2f = \sum_{i=1}^{5}(x_i - x_{i+2})^2 (indices mod 55). Expanding the effect of a move at the vertex carrying yy, all but a few terms cancel and

fnew−fold=2yS.f_{\text{new}} - f_{\text{old}} = 2yS.

Step 3 — y<0y < 0 and S>0S > 0, so ff drops by 2∣y∣S≥22|y|S \ge 2 at every move. It is a nonnegative integer, so there can be at most fstart2\tfrac{f_{\text{start}}}{2} moves. ■\blacksquare For instance, from (2,−1,3,0,−2)(2, -1, 3, 0, -2) with S=2S = 2 and f=32f = 32, the move at −1-1 gives (1,1,2,0,−2)(1, 1, 2, 0, -2) with f=28f = 28.

How to find it. Linear quantities are either invariant (the sum) or have no sign; the next candidates are quadratic. Among the natural quadratic sums, compute the change of each under one move and keep the one whose change factors through y⋅Sy\cdot S.

Side note
Where it goes wrong

“Every move decreases ff, so the process stops” is only valid if ff cannot decrease forever. The process “replace the number x∈(0,1]x \in (0, 1] on the board by x2\tfrac x2” decreases xx at every move and never stops. In Example 3 the decrease is at least 22 AND ff is a nonnegative integer; both facts are needed and both must be written.

Try it
Try it: an invariant product

The numbers 1,12,13,…,1101, \tfrac12, \tfrac13, \ldots, \tfrac1{10} are on a board. A move erases two numbers a,ba, b and writes a+b+aba + b + ab. After nine moves one number is left. What is it?

Show the answer

1+(a+b+ab)=(1+a)(1+b)1 + (a + b + ab) = (1 + a)(1 + b), so the product of (1+x)(1 + x) over the numbers on the board never changes. At the start it is ∏k=110(1+1k)=∏k=110k+1k=11\prod_{k=1}^{10}\left(1 + \tfrac1k\right) = \prod_{k=1}^{10}\tfrac{k + 1}{k} = 11. So the last number xx has 1+x=111 + x = 11: it is 1010, whatever the order of moves.