The numbers $1,2,3,\ldots ,2016,2017$ are written on a blackboard. On one turn, two numbers are erased, and their positive difference is written instead. Eventually, only one number remains.

What is the sum of all the possible values of the only remaining number?

The answer is 1018081.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

The key feature of this game is the following: The parity (even or odd) of the number of odd numbers on the board never changes.

This is easily seen by cases:

Now note that we start with $\frac{2017+1}{2} = 1009$ odd numbers on the board, which is an odd number of odd numbers. Therefore, the final number $N$ must be an odd number, and, in addition, it's easy to see that $0\leq N \leq 2017$ . It turns out that every odd number in that interval is possible, as we will now demonstrate:

Suppose I want to end up with some odd number $N$ with $1 \leq N \leq 2017$ . Then this number is originally on the blackboard. Find the largest two numbers $M_1, M_2$ such that neither equals $N$ . Erase them and replace them with their positive difference, which we note is either $1$ or $2$ . Do this until all the numbers on the board are $0$ , $1$ , $2$ , or $N$ (where we allow $N=1$ here as well). Now, if there are an even number of $2$ s, pair them up and subtract them to add more $0$ s to the board. If there are an odd number of $2$ s, do this until you end up with a single $2$ , which we then pair up with a $1$ (there is at least one $1$ , since we haven't used the original yet) to erase and replace with a $1$ . Now, by the parity argument I proved in the first part of this solution, there must be an even number of $1$ s on the board because we started with an odd number of odd numbers, $N$ is odd, and the $1$ s are the only other odd numbers on the board. Therefore, we may pair up the $1$ s on the board, erase them one pair at a time, and replace them with $0$ s. Obviously, now that the only nonzero number on the board is $N$ itself, that will be the final number.

This proves that every odd number $N$ such that $1 \leq N \leq 2017$ is a possible final number. Since $2017$ is the $1009$ th odd number, the sum of the first $1009$ odd numbers, and hence the answer, is $1 + 3 + 5 + 7 + \cdots + 2015 + 2017 = 1009^2 = \boxed{1018081}$