Glossary / Invariant
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 words” is hidden on all puzzles.
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?
No, and one count proves it, not trial and error.
Opposite corners of a chessboard are the same colour. So after the cut there are 32 dark squares left and only 30 light ones. And every domino, however you place it, covers one dark and one light square. However many dominoes you lay, there are always 2 more free dark squares than free light ones. To cover everything that difference would have to become zero, and it never changes. Try it yourself.
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.
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.
“Rigorous” is hidden on all puzzles.
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.
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.
“Deeper” is hidden on all puzzles.
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.
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.
An option that gives a player more than any other option of theirs, whatever the others choose.
A discount pays a coffee shop whatever the shop next door does, yet when both cut, each earns three times less than if both had kept their price.
A set of strategies where nobody gains by changing their own while the others keep theirs.
In the prisoner's dilemma both betray, though both would be better off silent: an equilibrium is not the best outcome.
Solving a game from the end: the last move first, then the one before it, back to the first.
In the centipede game logic says grab the pennies on the very first move, though playing on would give both of them hundreds, and real people almost never do it.
Everyone knows a fact, everyone knows that everyone knows, and so on without end.
Two generals can swap a thousand confirmations and still lack common knowledge, so neither dares to attack first.
If there are more items than boxes, some box ends up with at least two.
At least three people in Kyiv have exactly the same number of hairs on their heads, though nobody ever counted them.