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?
Answer
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.
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.
No comments:
Post a Comment