Invariants and conserved structure

Intuitive problem

Take an ordinary chessboard, 64 squares, and cut away two diagonally opposite corners. Can the remaining 62 squares be tiled by 31 dominoes, each domino covering two squares that share an edge? Trying it is discouraging: every attempt jams somewhere near the end, and each failure teaches nothing about the next attempt. Checking arrangements one by one misses the point, since the question is about every possible tiling at once. What is needed is a property that any tiling whatsoever would have to respect, and that the trimmed board refuses. Finding such a property, a feature of the situation that the process of laying dominoes cannot change, is the technique this entry develops.

Definition

Fix a process: a set of states, a starting state, and a collection of allowed moves, each transforming one state into another. An invariant is a function of the state that every allowed move leaves unchanged. If the function takes one value at the start and a different value at some target state, no sequence of moves reaches that target, however long or clever, because each step preserves the value and the target disagrees with it. A monovariant is the one-directional cousin: a quantity that every allowed move changes in the same direction, for instance a count that each move strictly lowers. Invariants rule states out; monovariants bound how long a process can run. One boundary is worth drawing in a single sentence: the symmetry of objects and of physical laws, and the conservation laws such symmetry forces, is the territory of the entry on symmetry and invariance, while this entry is the discrete proof technique, invariants constructed over a process's moves to decide what the process can reach.

Derivation

Start with the trimmed board and derive the answer. Color the 64 squares in the usual alternating pattern, 32 light and 32 dark. A domino covers two squares sharing an edge, and edge-adjacent squares differ in color, so every placement of a single domino covers exactly one light square and one dark square, wherever it lies and however it is turned. Now watch a tiling being built one domino at a time and track the quantity D, the number of light squares covered minus the number of dark squares covered. D begins at zero, and each placement adds one to both counts, leaving D at zero. D is an invariant of the building process. A complete tiling of the trimmed board, though, would cover all its squares, and diagonally opposite corners of a chessboard share a color, so removing them leaves 30 squares of one color and 32 of the other. At the end D would have to equal 30 minus 32, which is two away from zero. No sequence of placements gets there, so no tiling exists. One paragraph of counting closes a search that trial could not finish.

The same move generalizes past exact conservation. Often a useful quantity does change, while its remainder on division by two does not: if every allowed move shifts some count by an even step, zero or two at a time, then the count's parity, odd or even, is invariant even though the count itself wanders. A concrete instance is a board of plus and minus signs where a move rewrites signs by a fixed rule: the number of minus signs may fall or hold, but if every move changes it by an even amount, its parity at the start dictates its parity forever after, and states of the wrong parity are unreachable. The closing task below puts exactly this to work.

The monovariant argument deserves its own derivation, because the conclusion, termination, looks stronger than the premise. Suppose each state is assigned a value that is a non-negative integer, and every allowed move strictly decreases it. Let m be the value at the start. Integers that strictly decrease drop by at least one per step, so after k moves the value is at most m minus k, and after m moves it would have to be below zero, which no state supplies. The process therefore halts within m moves. What does the work here is the well-ordering of the non-negative integers: they contain no infinite strictly decreasing chain, so a quantity confined to them cannot fall forever. The integer-valuedness is the load-bearing hypothesis, and the Limits section shows the argument collapsing without it.

Visual representation

Picture the trimmed board in its two colors, the two missing corners both light. Lay one domino anywhere on what remains, upright or sideways. It covers one light square and one dark square, whichever placement you chose, and sliding it to any other legal position changes which squares are covered while leaving that one-and-one split intact. The whole impossibility proof is visible in this picture: a tiling would be 31 such one-and-one tiles, and the board offers 30 light squares against 32 dark.

Worked example

Two jugs stand at a tap, one holding 6 liters when full and one holding 9, with a drain nearby. The allowed moves: fill either jug to the brim, empty either jug completely, or pour from one jug into the other until the source runs dry or the destination fills. Can exactly 4 liters be measured out? Write gcd(6, 9) for the greatest common divisor of 6 and 9, the largest whole number dividing both, which is 3. The claim is that the amount of water in each jug is a multiple of 3 at every stage. It holds at the start, both jugs at zero. Filling sets a jug's content to 6 or to 9, both multiples of 3. Emptying sets it to zero. Pouring transfers either the entire source content or the destination's free space, its capacity minus its content; if both contents are currently multiples of 3, then each of those transfer amounts is a difference of multiples of 3 and hence a multiple of 3, and the two new contents are again multiples of 3. Divisibility by the gcd is preserved by every fill, every empty, and every pour, so every reachable amount is a multiple of 3, and 4 liters is unreachable. Notice how much the invariant licenses and no more: it rules 4 out, and it does not by itself certify that 3 can be produced. That takes an explicit construction, and one exists: fill the 9-liter jug and pour into the 6-liter jug until it fills, leaving 3 liters behind.

Limits and boundary conditions

An invariant proves impossibility or bounds a process's behavior; its absence proves nothing. Failing to find one does not make the target reachable, since the deciding invariant may simply be unfound, and there is no general recipe for producing one. Colorings, parities, sums, and divisibility by a gcd are the recurring candidates, and matching one to a problem is an art learned through practice. The monovariant side has a sharp boundary of its own: strict decrease forces termination only when the quantity's values are well-ordered, non-negative integers being the standard case. A strictly decreasing real quantity can decrease forever, as the sequence 1, 1/2, 1/4, 1/8 does, dropping at every step without end, so a termination argument that skips the well-ordering check has skipped the load-bearing step.

Common mistakes

Three errors recur. The first is anointing a quantity as invariant because it held steady across a few trials; the status must be earned by an argument covering every allowed move, checked case by case against the rules, since a single unexamined move type can break it. The second is reading a preserved invariant as a guarantee of success: if the start and the target agree on the invariant, nothing follows. Invariants only rule states out, and reaching a compatible target still demands an explicit construction, as the jug example showed for 3 liters. The third is concluding termination from any strictly decreasing quantity; without well-ordered values the argument fails, and the halving sequence above is the standing counterexample.

Build with it

Two puzzles, one for each tool. First, the sign board. A board holds 8 plus signs and 3 minus signs. One move erases any two signs and writes their product in their place: two pluses yield a plus, a plus and a minus yield a minus, two minuses yield a plus. Each move shrinks the board by one sign, so after ten moves a single sign remains. Propose the invariant, the parity of the number of minus signs, prove that each of the three move cases preserves it, and conclude which single sign can remain. Second, the splitting game. A pile of n coins sits on a table, where n is a positive whole number; a move takes any pile of two or more coins and splits it into two smaller piles whose sizes sum to the original, and piles of one coin admit no move. Identify a strictly decreasing non-negative integer monovariant and prove the game must end. Mind two traps: the number of piles rises with each move, so the pile count runs the wrong way; and the size of the largest pile only ever fails to rise, since splitting a smaller pile leaves it untouched, so it is non-increasing rather than strictly decreasing and fails the test. The quantity that works is the number of splits still available, n minus the current number of piles, which drops by exactly one each move; defend your choice with a check that it strictly decreases at every single move. Success is, for the sign board, a correct invariant with a preservation argument covering every move case and the correct final sign, and, for the splitting game, a correct monovariant with the well-ordering justification for why its decrease forces termination.