Oleg and (the ghost of) Erdös play the following game. Oleg chooses a non- negative integer a1 with at most 1000 digits.
In Round i the following happens:
Oleg tells the number ai to Erdös, who then chooses a non negative integer bi, and then Oleg defines ai+1 = |ai-bi| or ai+1 = ai + bi.
Erdös wins if a20 is a power of 10, otherwise Oleg wins.
Who is the winner, Oleg or Erdös?
at round i let the current number have value x mod 10 (i.e. the last digit is x)
now if x is not zero then at some point Erdos will need to make it zero otherwise he can
never achieve a multiple of 10 let alone a power of 10.
assertion
for any x with 0<x<=9 and any y with 0<=y<=9 we have either of the following is true
1) x+y is not congruent to 0 mod 10
2) both x-y and y-x are not congruent to 0 mod 10
proof:
simply go through all the possible combinations of x,y and you will see this holds for all of them
What this means is that at any given round, as long as the number does not start as a multiple
of 10 then no matter what Erdos chooses as his number Oleg can make a choice that prevents
the next number from being a multiple of 10. Thus Oleg can prevent the number for ever being
a power of 10 and Oleg wins.
This of course hinges on the number not being a multiple of 10 to begin with and this can be
prevented by Oleg making an appropriate initial choice.
Thus Oleg is the winner.
|
|
Posted by Daniel
on 2017-05-26 14:51:54 |
my solution
