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.)
 Erdös wins! | Comment 7 of 8 |

Say the number a1 has k digits.
We select the first k/2 digits, rounding if necessary, to produce a number, x.
Now we select that number which is 2x*10^(k/2)-a1, again rounding  if necessary.
This gives Oleg 2 choices, a k+1 digit number with k/2 zeros, or a k/2 digit number with no zeros.
If he selects the number with no zeros, we reiterate the exercise in the same way.
If he selects the number with zeros, we reiterate the exercise in the same way, ignoring the zeros.

In short order, Erdos gets a single digit number, with or without a lot of zeros, e.g.say a1 is 723828393839

a1 723828393839 723827606161 1447656000000 787678  723828 1447656
a2 787678 786322 1574000 1356  787 1574
a3 1356 1344 2700 12  135 270
a4 12 8 20 4  1 2
a5 4

a1 723828393839 723827606161 1447656000000 787678  723828 1447656
a2 1447656000000 1446344000000 2894000000000 1312000000  1447 2894
a3 2894000000000 2706000000000 5600000000000 188000000000  28 56
a4 5600000000000 4400000000000 10000000000000 1200000000000  5 10
a5 1200000000000 800000000000 2000000000000 400000000000  1 2
a6 400000000000

(Oleg could alternate choices but the principle is unaffected.)

Then, if the digit is:
Erdos        Oleg
1    1      2       0
go to 2
2    3      5       1
5    5     10      0

3    2      5       1
5    5     10      0

4    1      5       3
go to 5 go to 3

5    5     10      0

6    4     10      2
go to 2

7    3     10     4
go to 4
8   12    20     4
go to 2 go to 4
9   11    20     2
go to 2 go to 2

Say 10 turns for the reduction (1024=2^10), and 3 or 4 for working through the chart, 20 turns is very comfortable. (I didn't waste much time on the chart, probably could be improved.)

Edited on May 28, 2017, 2:19 am
 Posted by broll on 2017-05-28 02:07:12

 Search: Search body:
Forums (0)