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.

$\endgroup$
1

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ why would this be? $\endgroup$
    – fosho
    Jun 14, 2012 at 18:09
  • 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$
    – Henry
    Jun 14, 2012 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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