2017 numbers subtracting game

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:

• EVEN - EVEN = EVEN (no effect on odd numbers)
• ODD - ODD = EVEN (remove two odd numbers, so the parity of the number of odd numbers doesn't change)
• EVEN - ODD = ODD or ODD - EVEN = ODD (remove one odd number and then add one odd number, so the number of odd numbers doesn't change)

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}$