The numbers 1, 2, ..., 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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ If two numbers are equal, there difference won't be "positive" $\endgroup$– M.HerzkampOct 14, 2015 at 13:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
An alternate proof: consider the total of all the numbers on the blackboard. When you remove two numbers and write their difference what happens to this total?
Call the two numbers removed a and b. Order them so a ≥ b, so they will be replaced with a − b. When we make the replacement, the total changes by −a − b + (a − b) = −2b; that is, the total decreases by an even number.
Finally, the total of the starting numbers is even—it is equal to (500 × 501)/2 = 250 × 501 = 2 × (125 × 501)—and since the difference of two even numbers is always even, after any step the total will remain even. When one number is left it will be equal to the total, so it must 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.
It turns out that all numbers meeting both these criteria—that is, is all non-negative even numbers not greater than 500—are reachable: see Dr Xorile's answer for a proof.
answered Oct 13, 2015 at 16:16
-
$\begingroup$ Shouldn't the difference be strictly less than the larger number, since all numbers are positive? $\endgroup$– jpmc26Oct 14, 2015 at 4:22
-
3$\begingroup$ @jpmc26 After the first step you can make zero, e.g.
2 3 -> 1, then1 1 -> 0. $\endgroup$ Oct 14, 2015 at 4:24
$\begingroup$
$\endgroup$
4
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.
answered Oct 13, 2015 at 17:24
-
$\begingroup$ What if there's no pairing to give a difference of $1$, e.g. with $500$ when $n=499$? $\endgroup$– LawrenceOct 14, 2015 at 11:03
-
$\begingroup$ @Lawrence - pair 500 and 498 to leave 2. then pair that with a 1 $\endgroup$ Oct 14, 2015 at 11:38
-
1
-
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$– LawrenceOct 14, 2015 at 14:21