Maths WorkshopMaths problems with full solutions
Exercise 603Combinatorics › Counting principlesM1Added 4 Nov 2026

Replacing two numbers by their difference

#invariant#parity#board games

Statement

The numbers 1,2,…,101,2,\dots,10 are written on a board. A move consists of erasing two numbers aa and bb and writing ∣a−b∣|a-b| 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 22.

Invariant. A move replaces the two numbers a,ba,b by ∣a−b∣|a-b|, so the sum TT of the numbers on the board changes by
−(a+b)+∣a−b∣=−2min⁡(a,b),-(a+b)+|a-b|=-2\min(a,b),
which is even. Hence the parity of TT never changes.

Conclusion. At the start T=1+2+⋯+10=55T=1+2+\dots+10=55, which is odd. After nine moves, TT is the single remaining number, and it is odd.

Remark. The same argument works for 1,…,n1,\dots,n: the final number has the parity of n(n+1)2\frac{n(n+1)}2.

Lesson. Invariant: find a quantity (often a parity) that every allowed move preserves.