1
$\begingroup$

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.

  • 2
    This is an impartial game, which is defined as one where each player has the same moves from a given position. The http://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 http://www.amazon.com/Winning-Ways-Your-Mathematical-Plays/dp/1568811306/ref=sr_1_1?s=books&ie=UTF8&qid=1339708444&sr=1-1 The Wikipedia article also cites http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf which looks very good to me.2012-06-14

1 Answers 1

5

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.

  • 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 time2012-06-14