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?
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.Sign up to join this community
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.
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.