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 a_{i} to Erdös, who then chooses a non negative integer b_{i}, and then Oleg defines a_{i+1} = |a_{i}-b_{i}| or a_{i+1} = a_{i} + b_{i}.

Erdös wins if a_{20} is a power of 10, otherwise Oleg wins.

Who is the winner, Oleg or Erdös?

(In reply to

Thoughts by Brian Smith)

Hmm.

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.