KA-0167Parity arguments
5 points, difficulty 3 of 3Level 9–10about 165sThe numbers 1 to 10 are written on a board. You repeatedly rub out any two of them and write down their positive difference instead, until a single number is left. What can be said about that final number?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Look for something about the whole board that never changes when you make a move.
2The strategy
Replacing a and b by their difference changes the total by a + b - |a - b|, which is always an even amount.
3The full solution
The starting sum 1 + 2 + ... + 10 = 55 is odd, and every move changes the sum by an even number, so the final single number is odd.
Solution
The reliable way
Track the parity of the total. The starting sum is 1 + 2 + ... + 10 = 55, which is odd. A move replaces a and b by |a - b|, so the sum drops by a + b - |a - b|, which equals 2b or 2a - either way, an even number. Since the sum starts odd and only ever changes by an even amount, it stays odd forever. At the end one number remains and it IS the sum, so that number is odd. The transferable idea: when a process looks chaotic, look for a quantity it cannot change.
The elegant way
Differences preserve parity, so the whole board's parity is locked to the parity of 55 from the first move to the last.
Why this is on the test: An invariant turns a question with countless possible move orders into a single observation about parity.