4
$\begingroup$

Alice and Bob are playing a game. There is a pile of $2014$ stones. Alice and Bob alternate taking stones from the pile, with Alice going first. The number of stones Alice takes must be a power of $2$ (i.e: $1; 2; 4; :::$), and the number of stones Bob takes must be a power of $4$ (i.e: $1; 4; 16; :::$). The person who takes the last stone wins. Show that Alice has a winning strategy.

I saw this problem, but was unable to devise a strategy for Alice to win. Could I get some help?

Thank you!

$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

Represent the number $2014$ in binary:

$$\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{1}\color{red}{0}$$

If the binary representation of the number of remaining stones has a $\color{blue}{1}$ in an odd spot (counting from the right, corresponding to an odd power of two), then Bob cannot win in a single move (since he can only take even powers of two).

Try to show then that every move of Bob's either maintains or creates or reduces the number of $\color{blue}{1}$'s by at most one and that regardless of game position, Alice can always leave 1 or more $\color{blue}{1}$'s at the end of her turn (or end the game).

Since Bob cannot win, Alice must be the winner.

As for an explicit strategy for Alice, if on her turn there are no $\color{red}{1}$'s and only one $\color{blue}{1}$, then end the game by taking the $\color{blue}{1}$. Else, if there are some $\color{red}{1}$'s and no $\color{blue}{1}$'s, then choose to take a power of two corresponding to a $0$, thereby creating at least one $\color{blue}{1}$. Else, take any even power of two.

$\endgroup$
5
  • $\begingroup$ Why does "every move of Bob's either maintains or creates or reduces the number of $\color{blue}{1}$'s by at most one"? It seems $\color{red}{1}\color{blue}{0}\color{red}{0}\color{blue}{0}\color{red}{0}\color{blue}{0}\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{0} \to \color{red}{0}\color{blue}{1}\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{1}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{0}$ with Bob subtracting $2^6$ increases $\color{blue}1$ by two. Are you saying this kind of situations does not happen? $\endgroup$
    – Hans
    Sep 2, 2019 at 22:48
  • $\begingroup$ @Hans This is a rather old topic... I probably just misspoke. He either maintains, or creates (any number of $\color{blue}{1}$'s), or reduces (by at most one) the number of $\color{blue}{1}$'s. If he creates additional $\color{blue}{1}$'s this doesn't matter. The game will always terminate eventually, since the remaining number of stones always decreases. The point is that so long as there is at least one $\color{blue}{1}$, then Bob cannot win that turn and Alice can always ensure there is at least one $\color{blue}{1}$ at the end of her turn or win. $\endgroup$
    – JMoravitz
    Sep 2, 2019 at 23:14
  • $\begingroup$ That is clearer. It would be great if you will edit your answer to reflect the change. Also, it seems Alice's first-move privilege is irrelevant to her winning strategy. This problem setup is a bit ambiguous. The rule does not specify if Alice wins if $10$ (in binary) is left and it is Bob's turn? Of course, your specification "if Bob cannot win, Alice must be the winner" would resolve that ambiguity. But that is different from the original setup, albeit the difference is slight. $\endgroup$
    – Hans
    Sep 3, 2019 at 20:27
  • $\begingroup$ @hans if there are two stones left and it is Bob's turn, then Bob's only legal play is to take one stone. Then alice takes the remaining stone and wins $\endgroup$
    – JMoravitz
    Sep 3, 2019 at 20:33
  • $\begingroup$ Oh, right. I forgot Bob was allowed to take $1$ stone. It seems that Alice wins even if she moves second. Would you agree with that? $\endgroup$
    – Hans
    Sep 4, 2019 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .