All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Oleg or Erdös? (Posted on 2017-05-26)
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?

Comments: ( Back to comment list | You must be logged in to post comments.)
 my solution | Comment 1 of 8
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

 Search: Search body:
Forums (0)