7.4 Parity and invariants

Some puzzles allow many moves, making it hard to list every reachable state. Instead, look for a feature that cannot change. If the starting state has one value of that feature and the target has another, no sequence of permitted moves can connect them. This is an invariant argument. Parity—whether an integer is even or odd—is often the simplest feature to test.

This is intermediate discrete reasoning. MIT's state-machine notes develop the invariant method, and its modular-arithmetic notes explain parity as a remainder. You only need the even/odd rules to begin.

A basic idea: what survives every move?

Colour a $4\times4$ board like a chessboard. Every horizontal or vertical domino covers one dark and one light square, regardless of where it is placed. Remove two opposite corners. They have the same colour, so the board now has $6$ squares of that colour and $8$ of the other. Seven dominoes would have to cover seven of each. That cannot happen, even if you try many clever placements.

A quick tour of the method

An integer's parity is its remainder after division by $2$: even has remainder $0$, odd has remainder $1$. Adding an even number preserves parity; adding an odd number changes it. More generally, an invariant is a quantity or property that every allowed move preserves. To use one:

1. Define the feature precisely for any state.
2. Check every type of legal move, not just one example, preserves it.
3. Compare the feature in the starting state and the proposed target.

Some features alternate rather than stay fixed. A single horizontal or vertical grid step changes $x+y$ by $1$ or $-1$, so the parity of $x+y$ flips after every step. Knowing the number of steps then determines which colour of a checkerboard the walker can reach. This is still a useful state rule, but call it an alternating property rather than a preserved invariant.

An invariant can prove impossibility when the values disagree. Matching values do not prove that a path or tiling exists; other obstacles may remain.

Application 1: missing corners

Can seven $1\times2$ dominoes tile a $4\times4$ checkerboard after two opposite corners are removed?

1. The original board has eight squares of each colour. Opposite corners on this even-sized board have the same colour.
2. Removing them leaves $6$ of that colour and $8$ of the other.
3. Each domino always covers one square of each colour. Seven dominoes would cover $7$ and $7$, so the tiling is impossible.

Application 2: an exact number of grid moves

A walker starts at $(0,0)$ and makes exactly $11$ moves, each one unit north, south, east, or west. Can it finish at $(2,2)$?

1. At the start, $x+y=0$ is even. Each move flips its parity.
2. After an odd number of moves, $x+y$ must be odd.
3. At $(2,2)$, $x+y=4$ is even. Therefore no route of exactly $11$ moves can end there. The point is reachable in four moves, but the specified move count is not.