In one sentence
When everything keeps changing, look for the quantity that does not. If that quantity is different at the start and at the goal, you can never get there, however many moves you make and however you make them.
What doesn't change in the sign grid
Step 1 / 5- Start: 1 minus sign
There is just one , and the goal is . It looks so close.
This chapter has three tools: invariants (to prove you can never get there), quantities that only go down (monovariants, to prove the process must stop) and working backwards (to find the winning moves in a game).
Stop 1 · You choose the invariant
Change the grid to , with the minus sign in the center.
Predict first
A grid with only in the center. Flipping whole rows or columns, can you make it all ? Is “the parity of the number of minus signs” still an invariant here?
A row has only numbers: minus signs become , a change of , which is odd. The old invariant no longer works.
Try the candidate quantities in the tracker one by one. Which one survives? Why does it never change?
When a row or column passes through the top-left block, it passes through exactly of its squares; two numbers change sign together, so the product stays the same. The product of the four numbers in this block starts at (the center square is in it), but it is when everything is . Invariants don't come ready-made: you design them by looking at the moves.
Stop 2 · Numbers on the blackboard
The blackboard shows . Each move erases two numbers and writes their difference.
Predict first
Keep going until only one number is left. Could that number be ?
Erasing , and writing lowers the total by , which is twice the smaller of the two numbers: an even number. So the parity of the sum never changes. At the start, is odd, so the last number is odd too, and cannot be .
Play a few times yourself, erasing in a different order each time, and check with the tracker.
Change the rule: erase , and write . This time an invariant pins down even the last number.
Stop 3 · Flipping cups
Each move flips cups. If of them were facing up, the number facing up changes by , which is even. The number facing up starts at , so it is always odd and can never reach .
Break it
Counterexample lab: remove one condition
Conclusion: The parity of the number facing up never changes, so cups can never all be turned down ← still true?
Each move flips cups. Track “Up count odd or even”: however you flip, it stays “odd”.
Change it to flipping cups each move. Now the parity changes at every move and the invariant is gone, and this time it can be done. What is the smallest number of moves?
moves are enough: for example flip cups 1, 2, 3, then 3, 4, 5 (cup 3 goes back up), and finally 3, 6, 7. moves are not enough: moves make at most flips, but each of the cups has to be flipped at least once.
Stop 4 · It has to stop
Some problems don't ask “can you get there?” but “could this go on forever?”. Then you look for a whole number that gets strictly smaller at every move but can never go below .
Swap a neighboring pair where the left one is taller: that pair is no longer an inversion, and no other pair of people changes which of them is on the left. So the number of inversions goes down by exactly . It is a non-negative whole number, so it cannot go down forever: the process must stop, and it takes exactly as many moves as there were inversions at the start, whatever order you swap in.
Stop 5 · Games: work backwards from the end
stones. Two players take turns, taking , or stones each time, and whoever takes the last stone wins. First play a game against the computer. It never makes a mistake.
How the losing positions are worked out
Step 1 / 5- 0 stones left
It is your turn, but there are no stones left: your opponent took the last one. With stones left, the player to move loses. Mark it “L”.
When the rules change, the losing positions change too, but the method stays the same.
Predict first
Now each turn you may take only , or stones (not ), and there are stones. Do you want to go first or second?
Work backwards from : is L; is W (take ); is L (you can only take , leaving for your opponent); and are W; is W (take , leaving ); is W (take , leaving ); is L; is W; is L … The pattern repeats every , and the losing positions are the numbers with remainder or on division by . is a losing position, so let the computer go first.
Some games need no table at all: symmetry wins them.
The first player takes the coin in the very middle (with an even number of coins, the middle two), leaving two equal runs on the left and right. After that, whatever your opponent takes on one side, you take the mirror image on the other side. As long as your opponent has a move, so do you, so the last coin is always yours.
Practice
The blackboard shows . Each move erases two numbers and writes their difference. Is the one number left at the end odd or even?
cups all face up, and each move must flip exactly of them. What is the smallest number of moves that turns them all face down?
A pile has stones. Two players take turns, taking to stones each time, and whoever takes the last stone wins. You go first. How many stones should you take on your first move to be sure of winning?
Five people stand in a row; their heights, numbered from left to right, are . Each move swaps two neighbors where the left one is taller. To line them up from shortest to tallest, exactly how many swaps are needed?
A pile has stones. Two players take turns, taking only , or stones each time, and whoever takes the last stone wins. Do you want to go first or second?