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.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ 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. $\endgroup$– Ross MillikanJun 14, 2012 at 21:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
-
1$\begingroup$ @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. $\endgroup$ Jun 14, 2012 at 18:14
-
1$\begingroup$ +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. $\endgroup$ Jun 14, 2012 at 18:31
-
2$\begingroup$ 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 $\endgroup$– HenryJun 14, 2012 at 19:45