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.)
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       
        
                              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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information