The Difference Game

The problem

The numbers $1, 2, 3, \dots, 1000$ are written on a board. A move consists of choosing any two numbers, erasing them, and writing their difference on the board. Every move reduces the count of numbers by one, so after 999 moves a single number remains.

Is the last number even or odd? Does your answer depend on how the moves are played?

Before you begin

Play the game with a small set first, say $1, 2, 3, 4, 5$. Play it two or three different ways. Something curious happens with the final number — see if you can catch it.

1. When two numbers get replaced by their difference, what happens to the sum of everything on the board?
2. Compare $a + b$ and $a - b$. What do they share?
3. Can you find a quantity that never changes, no matter how the game is played?

Dissect the task

1. This problem is still elementary: no theorem is needed. Yet it sits one tier above the doors. What is the extra conceptual reach it asks for?
2. The habit of hunting for a quantity that does not change is called looking for an invariant. Where else in school mathematics could a child practise this habit?