KA-0098Invariants and monovariants
5 points, difficulty 3 of 3Level 5–6about 165sThe numbers 1 to 8 are on a board. A move rubs out two of them and writes their difference, larger minus smaller. After seven moves one number is left. Can it be 1?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Watch what happens to the total.
2The strategy
Add everything on the board and see how one move changes that total. Replacing a and b by their difference always changes it by the same kind of amount.
3The full solution
The total starts at 1 + 2 + ... + 8 = 36, which is even. A move changes the total by twice the smaller number, so it stays even and the last number cannot be odd.
Solution
The reliable way
Track the total of everything on the board. It starts at 1 + 2 + ... + 8 = 36, which is even. A move replaces a and b with a - b, so the total drops by (a + b) - (a - b) = 2b, always an even amount. The total therefore stays even for ever, and the single number left at the end is that total, so it is even. Since 1 is odd, it can never be the last number. The transferable idea: a quantity no move can change decides the answer before you try anything.
The elegant way
Differences preserve parity, so the last number always matches the parity of 1 + 2 + ... + 8, which is even.
Why this is on the test: Invariants replace an unbounded search with one observation, and choice D punishes stopping at the first example you happen to find.