Alice and Bob picking game

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


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