6
$\begingroup$

Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. Thereafter, in each turn a player must pick at least one stone, but no more stones than were picked in the immediately preceding turn. The player who takes the last stone wins. With what property of $N$, will Alice win? When will Bob win?

For odd $N$ the outcome is quite clear, as Alice will start by picking one stone and will enforce the win. But what then?

$\endgroup$
  • $\begingroup$ "uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned. $\endgroup$ – Peter Jul 17 '18 at 18:20
  • 2
    $\begingroup$ But he told you the strategy $\endgroup$ – Aqua Jul 17 '18 at 18:46
  • $\begingroup$ Why did this post even get a close vote? The OP has included some effort. $\endgroup$ – Batominovski Jul 17 '18 at 19:03
  • $\begingroup$ Perhaps upvoting will help? $\endgroup$ – Aqua Jul 17 '18 at 19:06
  • $\begingroup$ Do you know the so called Nin games? $\endgroup$ – Cesareo Jul 17 '18 at 20:04
6
$\begingroup$

Alice wins when $N$ is not a power of 2.

Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.

Alice's strategy: If there are $m$ stones left, Alice picks $2^{i(m)}$ stones.

Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $b\ge 2^j$. On the other hand by the rules of the game $b\le 2^j$. Therefore $b = 2^j$.

But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.

This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.

Let us verify that $2^{i(m)} \le b$. We will do it by showing that $b$ is divisble by $2^{i(m)}$.

Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $b\le 2^j$. Let us show that $i(m) \le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $b\le 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^{j + 1} + m) \ge j + 1$.

Thus we have proved that $i(m) \le j$. This means $2^j + b + m$ is divisble by $2^{i(m)}$, as well as $m$. Hence $b$ is also divisble by $2^{i(m)}$ as required.

Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j \le a$.

$\endgroup$
  • $\begingroup$ What if $N=2^i$? $\endgroup$ – Steve Kass Jul 17 '18 at 18:48
  • 1
    $\begingroup$ @Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone. $\endgroup$ – Praneet Srivastava Jul 17 '18 at 18:50
  • $\begingroup$ @Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please? $\endgroup$ – RandyR Jul 17 '18 at 23:22
  • $\begingroup$ @RandyR, rewrote the answer to avoid induction. $\endgroup$ – Sasha Kozachinskiy Jul 18 '18 at 7:46
  • $\begingroup$ @Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner! $\endgroup$ – RandyR Jul 18 '18 at 8:22
4
$\begingroup$

First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^{k+1}$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.

If $N \neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)

$\endgroup$
  • $\begingroup$ Thank you for providing proof via induction - easy to understand and very well written! $\endgroup$ – RandyR Jul 18 '18 at 8:35

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.