# Winning strategy

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.

-
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

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.

-
why would this be? – fosho Jun 14 '12 at 18:09
@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 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
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