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₂₀ is a power of 10, otherwise Oleg wins.

Who is the winner, Oleg or Erdös?

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       
        
                              2*x*10^6-a1        Add                ||           x              2x
 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     
             Add     ||    
 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