Math paradoxes

Glossary / Invariant

Glossary · invariant

Why won't any attempt help here?

Some puzzles make you want to try again and again: rearrange, re-lay, flip it differently. It feels like you are just one lucky move short. But sometimes a quantity doesn't change with any move, while at the end it would have to be different. Then the goal can never be reached, and what proves it is not a thousand failed attempts but one count. Such a quantity is called an invariant.

In plain wordspictures, analogies, small numbers

“In plain words” is hidden on all puzzles.

A chessboard without two corners

Two squares in opposite corners have been cut out of an ordinary 8 × 8 chessboard. That leaves 62 squares. You have 31 dominoes, and each covers exactly two neighbouring squares, side by side or one above the other.

Can you cover all 62 squares with 31 dominoes without overlaps?

Tap a square, then a neighbouring one: a domino goes down. Tap a domino to remove it.

The computer doesn't guess: it finds the largest possible number of dominoes with an exact algorithm. On the board without opposite corners it too stops at 30, and the two free squares are always dark. On the board without neighbouring corners one dark and one light square are cut, the difference is zero from the start, and 31 dominoes fit.

Seven cups

There are seven cups on the table, all upside down. In one move you must flip exactly two of them, any two. Can you get all seven the right way up? Pick two cups and they flip.

When you flip two, the number of upside-down cups changes by 2 or not at all: both off the rim, both onto it, or one each way. So an odd number stays odd, and 0 is even. You started at 7, so zero never comes. But allow three flips per move and the parity changes every time: the invariant is gone and the goal can be reached. An invariant is a property not of the puzzle itself but of the moves it allows.

Rigoroustables, charts, formulas

“Rigorous” is hidden on all puzzles.

What an invariant is

An invariant is a quantity or property that no allowed move changes. The gap between free dark and light squares, the parity of upside-down cups, a sum, a remainder after dividing by 3. If the invariant has one value at the start and would need another at the desired end, that end cannot be reached, however long you try.

  • Start from the move, not the goalWrite down exactly what one move does: covers two neighbouring squares, flips two cups, swaps two tiles. The invariant is found among the things that move preserves.
  • The usual suspectsParity (even or odd), a colouring in two or more colours, a sum of numbers, a remainder. Parity works most often.
  • It proves "no", not "yes"If the invariant differs between start and finish, the goal is unreachable. If it matches, that promises nothing: there may be another invariant you missed, or simply not enough moves.
  • Failed attempts are not proofA hundred failures only say you haven't found a layout. An invariant says there is none. That's why it's worth a minute before the tenth attempt.

A 15 puzzle that won't solve

Fifteen tiles in a 4 × 4 box and one empty space. A move slides a neighbouring tile into the gap. Here everything is in order except the last two: 15 stands before 14. It looks like the easiest position imaginable: just swap two tiles. Try it.

The counter tracks two things. "Disorder": how many pairs of tiles are in the wrong order when you read row by row, left to right, a bigger one before a smaller one. And the row number of the empty space. A move along a row changes neither. A move up or down carries a tile past three others: the disorder changes by 1 or 3, and the gap's row by 1. Together that's an even change, so the parity of the sum is an invariant. In the solved puzzle the sum is 0 + 4 = 4, even. With 14 and 15 swapped it is 1 + 4 = 5, odd. However long you slide, it won't solve.

Where invariants live

  • Double-entry bookkeepingEvery transaction is recorded twice, as a debit and a credit, so assets always equal liabilities plus equity. The equality is an invariant of every entry. If the books don't balance, there's a mistake somewhere, and you can hunt for it without checking every figure. Luca Pacioli described the method in 1494 in "Summa de arithmetica".
  • The Rubik's cubeTake a cube apart and reassemble the pieces at random, and only one arrangement in 12 can be solved. A single twisted corner, a single flipped edge or two swapped pieces break one of three invariants (2 × 3 × 2 = 12), and no turning of the faces will fix it.
  • ProgrammingA loop invariant is a statement true before every step of a loop. In binary search it's "the target, if present, lies between the left and right bounds". Robert Floyd (1967) and Tony Hoare (1969) made such statements the basis for proving a program correct.
  • Conservation lawsThe energy of a closed system is an invariant of everything that happens inside it. That's why a perpetual motion machine needs no check of its blueprint: the Paris Academy of Sciences decided back in 1775 not to examine such proposals.
Deepergeneralisations, theory, history

“Deeper” is hidden on all puzzles.

The formula and the monovariant

f(T(x)) = f(x)  for every state x and every allowed move T

It follows at once: if f(start) ≠ f(goal), no sequence of moves leads from start to goal. The function f can be a number, a remainder, a colour, anything you can compare.

A close relative is the monovariant: it doesn't stay put but decreases every time. If it is a non-negative whole number, the process has to stop. Example: the same disorder from the 15 puzzle. If you keep swapping two neighbouring items of a list that are out of order, the disorder drops by exactly 1. So the sorting is bound to finish, and it takes exactly as many swaps as there were out-of-order pairs.

Stronger colourings

Two colours are enough for dominoes. Longer pieces need more. Can a 10 × 10 board be covered with 1 × 4 strips? The area divides: 100 = 25 × 4. Colour the squares along diagonals in four colours in turn: a square's colour is the remainder when its row number plus column number is divided by 4. Any 1 × 4 strip, lying or standing, covers one square of each colour. So a covered board would need equal numbers of each colour, 25 apiece. There are 25, 26, 25 and 24. It can't be done.

And sometimes the invariant is the whole story. Gomory's theorem: cut any dark and any light square out of an 8 × 8 chessboard, and the rest can always be covered with 31 dominoes. Here the colour gap is the only obstacle. A computer easily checks all 32 × 32 = 1,024 such pairs: every one works.

Where these puzzles came from

  • The chessboardThe cut-corners puzzle was posed by the philosopher Max Black in his logic textbook "Critical Thinking" (1946). Solomon Golomb (1954) and Martin Gardner in his Scientific American column (1957) discussed it, and in 1964 John McCarthy proposed it as "a tough nut" for proof-finding programs: brute force breaks down, while a person sees the colours.
  • The 15 puzzleThe puzzle was invented by Noyes Chapman, a postmaster from Canastota, New York, and in 1880 all of America went crazy for it. As early as 1879 William Johnson and William Story proved in the American Journal of Mathematics that exactly half of all arrangements can't be solved. Sam Loyd later passed himself off as its inventor and offered 1,000 dollars to whoever put 14 and 15 back in order.
  • Symmetries and conservationIn 1918 Emmy Noether proved that every conservation law in physics comes from a symmetry: energy is conserved because the laws don't change over time, momentum because they are the same at every point in space. Invariant and symmetry turned out to be two sides of one idea.

Where it shows up

More on “Games and logic”

All terms →