2017 numbers subtracting game

Probability Level pending

The numbers 1 , 2 , 3 , , 2016 , 2017 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.

1 solution

Brian Moehring
Feb 12, 2017

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

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...