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.)
re: Thoughts | Comment 6 of 8 |
(In reply to Thoughts by Brian Smith)


Brian:  I think that you mean let p_i be the smallest tenth power that is greater than or equal to a_i.   This is necessary in order that b_i is non-negative.  At any rate, it does not work, as you pointed out.

However, you made me think.

If a_1 = 2, Erdos can win in three moves.
let b_1 = 3.  In order to avoid a power of 10, Oleg must add it, making a_2 = 5
let b_2 = 5.  In order to avoid a power of 10, Oleg must subtract it, 
making a_3 = 0
Now Erdos can make b_3 any power of 10.  Say 1 million.

In other words, Oleg must avoid 0, which leads to a win in one more turn.
Oleg must avoid 5*10^n, which leads to a win in two turns.
Oleg must avoid 25*10^n, which leads to a win in three turns.
Oleg must avoid 125*10^n, which leads to a win in four turns.
Given all these numbers which he must avoid, it seems that Erdos might be able to force him to subtract, and continually reduce his number.

But in 20 turns?  More improvement is clearly needed.

  Posted by Steve Herman on 2017-05-27 22:28:50
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information