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?
(In reply to
re(2): my solution by Daniel)
here is my logic table, O is the initial number and E is the number Erdos chooses
column descriptions
A) 0 if the number Erdos chooses is greater than the initial number and 1 otherwise. This is used to determine if |O-E| mod 10 is O-E mod 10 or E-O mod 10
B) O mod 10
C) E mod 10
D) |O-E| mod 10
E) O+E mod 10
F) If this is one then this indicates that either D or E is either 0 or 5. In other words, that combination of values Erdos is able to force the new number to be either 0 or 5 mod 10.
A B C D E F
0 1 0 9 1 0
0 1 1 0 2 0
0 1 2 1 3 0
0 1 3 2 4 0
0 1 4 3 5 0
0 1 5 4 6 0
0 1 6 5 7 0
0 1 7 6 8 0
0 1 8 7 9 0
0 1 9 8 0 0
0 2 0 8 2 0
0 2 1 9 3 0
0 2 2 0 4 0
0 2 3 1 5 0
0 2 4 2 6 0
0 2 5 3 7 0
0 2 6 4 8 0
0 2 7 5 9 0
0 2 8 6 0 0
0 2 9 7 1 0
0 3 0 7 3 0
0 3 1 8 4 0
0 3 2 9 5 0
0 3 3 0 6 0
0 3 4 1 7 0
0 3 5 2 8 0
0 3 6 3 9 0
0 3 7 4 0 0
0 3 8 5 1 0
0 3 9 6 2 0
0 4 0 6 4 0
0 4 1 7 5 0
0 4 2 8 6 0
0 4 3 9 7 0
0 4 4 0 8 0
0 4 5 1 9 0
0 4 6 2 0 0
0 4 7 3 1 0
0 4 8 4 2 0
0 4 9 5 3 0
0 5 0 5 5 1
0 5 1 6 6 0
0 5 2 7 7 0
0 5 3 8 8 0
0 5 4 9 9 0
0 5 5 0 0 1
0 5 6 1 1 0
0 5 7 2 2 0
0 5 8 3 3 0
0 5 9 4 4 0
0 6 0 4 6 0
0 6 1 5 7 0
0 6 2 6 8 0
0 6 3 7 9 0
0 6 4 8 0 0
0 6 5 9 1 0
0 6 6 0 2 0
0 6 7 1 3 0
0 6 8 2 4 0
0 6 9 3 5 0
0 7 0 3 7 0
0 7 1 4 8 0
0 7 2 5 9 0
0 7 3 6 0 0
0 7 4 7 1 0
0 7 5 8 2 0
0 7 6 9 3 0
0 7 7 0 4 0
0 7 8 1 5 0
0 7 9 2 6 0
0 8 0 2 8 0
0 8 1 3 9 0
0 8 2 4 0 0
0 8 3 5 1 0
0 8 4 6 2 0
0 8 5 7 3 0
0 8 6 8 4 0
0 8 7 9 5 0
0 8 8 0 6 0
0 8 9 1 7 0
0 9 0 1 9 0
0 9 1 2 0 0
0 9 2 3 1 0
0 9 3 4 2 0
0 9 4 5 3 0
0 9 5 6 4 0
0 9 6 7 5 0
0 9 7 8 6 0
0 9 8 9 7 0
0 9 9 0 8 0
1 1 0 1 1 0
1 1 1 0 2 0
1 1 2 9 3 0
1 1 3 8 4 0
1 1 4 7 5 0
1 1 5 6 6 0
1 1 6 5 7 0
1 1 7 4 8 0
1 1 8 3 9 0
1 1 9 2 0 0
1 2 0 2 2 0
1 2 1 1 3 0
1 2 2 0 4 0
1 2 3 9 5 0
1 2 4 8 6 0
1 2 5 7 7 0
1 2 6 6 8 0
1 2 7 5 9 0
1 2 8 4 0 0
1 2 9 3 1 0
1 3 0 3 3 0
1 3 1 2 4 0
1 3 2 1 5 0
1 3 3 0 6 0
1 3 4 9 7 0
1 3 5 8 8 0
1 3 6 7 9 0
1 3 7 6 0 0
1 3 8 5 1 0
1 3 9 4 2 0
1 4 0 4 4 0
1 4 1 3 5 0
1 4 2 2 6 0
1 4 3 1 7 0
1 4 4 0 8 0
1 4 5 9 9 0
1 4 6 8 0 0
1 4 7 7 1 0
1 4 8 6 2 0
1 4 9 5 3 0
1 5 0 5 5 1
1 5 1 4 6 0
1 5 2 3 7 0
1 5 3 2 8 0
1 5 4 1 9 0
1 5 5 0 0 1
1 5 6 9 1 0
1 5 7 8 2 0
1 5 8 7 3 0
1 5 9 6 4 0
1 6 0 6 6 0
1 6 1 5 7 0
1 6 2 4 8 0
1 6 3 3 9 0
1 6 4 2 0 0
1 6 5 1 1 0
1 6 6 0 2 0
1 6 7 9 3 0
1 6 8 8 4 0
1 6 9 7 5 0
1 7 0 7 7 0
1 7 1 6 8 0
1 7 2 5 9 0
1 7 3 4 0 0
1 7 4 3 1 0
1 7 5 2 2 0
1 7 6 1 3 0
1 7 7 0 4 0
1 7 8 9 5 0
1 7 9 8 6 0
1 8 0 8 8 0
1 8 1 7 9 0
1 8 2 6 0 0
1 8 3 5 1 0
1 8 4 4 2 0
1 8 5 3 3 0
1 8 6 2 4 0
1 8 7 1 5 0
1 8 8 0 6 0
1 8 9 9 7 0
1 9 0 9 9 0
1 9 1 8 0 0
1 9 2 7 1 0
1 9 3 6 2 0
1 9 4 5 3 0
1 9 5 4 4 0
1 9 6 3 5 0
1 9 7 2 6 0
1 9 8 1 7 0
1
9
9
0
8
0
Now to make it easier to read I took the total of column F for each value in column B. What this tells us is that if the sum is 0, then if the initial value is congruent the given value in the table mod 10 then Erdos is not able to force the number to be either 0 or 5 mod 10.
Initial Value Mod 10
ways Erdos can force it to be 0,5 mod 10
1 0
2 0
3 0
4 0
5 4
6 0
7 0
8 0
9 0
As you can see, as long as Oleg does not make an initial choice of 5 mod 10, then Oleg can always avoid a number which is congruent to 0 or 5 mod 10 and thus the number will never be a power of 10.
|
|
Posted by Daniel
on 2017-05-27 09:59:44 |
re(3): my solution
