Alice and Bob picking game

Question

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?

Answer 1

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$.

Answer 2

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.)