Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a winning strategy for player one or two in the following scenario: The game begins with the number 2012. In one turn, a player can subtract from the current number any natural number less than or equal to it that is a power of 2. The player who reaches 0 wins.

share|improve this question
2  
This is an impartial game, which is defined as one where each player has the same moves from a given position. The en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem shows that each position is equivalent to a Nim heap and how to calculate which one. There is a good discussion in vol 1 of Winning Ways amazon.com/Winning-Ways-Your-Mathematical-Plays/dp/1568811306/… The Wikipedia article also cites math.ucla.edu/~tom/Game_Theory/comb.pdf which looks very good to me. –  Ross Millikan Jun 14 '12 at 21:15

1 Answer 1

up vote 5 down vote accepted

It seems a player loses if the number is a multiple of 3 on his/her turn. Indeed, in that situation it is impossible to subtract a power of 2 and obtain a difference that is again a multiple of 3. On the other hand, if the number is not a multiple of 3, then the player can force the difference to become a multiple of 3 by playing either 1 or 2.

In particular, the first player wins in this game, where the starting number 2012 is not a multiple of 3. He/she starts by playing 2 (or 512 if he/she wants to go a little faster) and then just makes sure to make the difference a multiple of 3 at the end of all his/her turns.

share|improve this answer
    
why would this be? –  fosho Jun 14 '12 at 18:09
1  
@Daniel: Try to convince yourself that if I have left a multiple of 3, no matter what move the other player makes it will not be a multiple of 3 and I can restore it to a multiple of 3. Then since the goal is a multiple of 3, the other player can never reach it and I will. –  Ross Millikan Jun 14 '12 at 18:14
1  
+1 Well spotted! It's kind of a drag that the game is essentially equivalent to a simpler one, where the only two moves allowed by the rules are to subtract one or two. Modulo three does that. –  Jyrki Lahtonen Jun 14 '12 at 18:31
2  
so for a slow winning game subtract $1$ or $2$ each time and for a fast winning game subtract $2^{\lfloor \log_2 n \rfloor}$ or $2^{\lfloor \log_2 n \rfloor - 1}$ each time –  Henry Jun 14 '12 at 19:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.