13
$\begingroup$

The numbers $ 1, 2, \ldots, 500 $ are written on a blackboard. Each minute any two numbers are wiped out and their positive difference is written instead. At the end only one number remains.

Which values can this final number take?

$\endgroup$
  • $\begingroup$ If two numbers are equal, there difference won't be "positive" $\endgroup$ – M.Herzkamp Oct 14 '15 at 13:23
20
$\begingroup$

Parity

  • If you remove any two even numbers, their difference will also be an even number. The total number of odd numbers will remain the same.

  • If you remove any two odd numbers, their difference will be an even number. The total number of odd numbers will decrease by two.

  • If you remove an even and an odd number, their difference will be an odd number. The total number of odd number will remain the same (remove one, add one).

Thus we can see that the number of odd numbers at any step is equivalent to the starting count modulo two. Therefore if you start with an odd number of odd numbers, the final result will be odd, otherwise it will be even. In this case we have an even number of odds, so the final number will be even.

Magnitude

If you remove any two non-negative numbers, their positive difference must be less than or equal to the larger of the two. Therefore the final result can be at most 500.


Playing around with a quick computer simulation of the problem, I have found that all numbers that satisfy the above two criteria are possible, that is all non-negative even numbers not greater than 500.

Later I'll come back and try to construct a proof that all such numbers are reachable.

$\endgroup$
  • $\begingroup$ Shouldn't the difference be strictly less than the larger number, since all numbers are positive? $\endgroup$ – jpmc26 Oct 14 '15 at 4:22
  • 2
    $\begingroup$ @jpmc26 After the first step you can make zero, e.g. 2 3 -> 1, then 1 1 -> 0. $\endgroup$ – 2012rcampion Oct 14 '15 at 4:24
18
$\begingroup$

Building on @2012rcampion's answer, here's a simple constructive proof that any even number is reachable.

Take the (even) number that you want to reach (say $n$) and put it aside. Then take the difference between all the pairs $(500,499), (498,497),\ldots,(n+2,n+1)$, and $(n-1,n-2),(n-3,n-4),\ldots,(3,2)$.

That will give you an odd number of 1's. You'll also still have the original 1, so the total number of 1's is even (when the number of odd numbers is even).

You then pair them up and take the difference which gives you a bunch of 0's. Then you boil it down to $n$.

A similar approach works when there's an odd number of odd numbers, except that you're left with one 1 at the end, so you can get to $n-1$ in that way.

$\endgroup$
  • $\begingroup$ What if there's no pairing to give a difference of $1$, e.g. with $500$ when $n=499$? $\endgroup$ – Lawrence Oct 14 '15 at 11:03
  • $\begingroup$ @Lawrence - pair 500 and 498 to leave 2. then pair that with a 1 $\endgroup$ – Collett89 Oct 14 '15 at 11:38
  • $\begingroup$ @Lawrence 499 is not an even number. $\endgroup$ – Taemyr Oct 14 '15 at 13:54
  • 1
    $\begingroup$ @Taemyr Yes, though for odd numbers, Collett89's observation gets you to $n-1$, similar to the last point in Dr Xorile's answer. $\endgroup$ – Lawrence Oct 14 '15 at 14:21

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.