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

Home > Games
Oleg or Erdös? (Posted on 2017-05-26) Difficulty: 4 of 5
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?

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information