Exercise 603Combinatorics › Counting principlesM1Added 4 Nov 2026
Replacing two numbers by their difference
#invariant#parity#board games
Statement
The numbers are written on a board. A move consists of erasing two numbers and and writing instead. After nine moves, a single number remains. Prove that it is odd.
Hint
How does the parity of the sum of all numbers on the board change after a move?
Show solutionHide solution
Solution
Idea. Find a quantity that a move cannot change, at least modulo .
Invariant. A move replaces the two numbers by , so the sum of the numbers on the board changes by
which is even. Hence the parity of never changes.
Conclusion. At the start , which is odd. After nine moves, is the single remaining number, and it is odd.
Remark. The same argument works for : the final number has the parity of .
Lesson. Invariant: find a quantity (often a parity) that every allowed move preserves.