Game of coins - find the winning strategy

Question

Alice and Bob play a game. There is a box with $n \geq 2$ coins in it. Bob starts first and he can take any amount of coins from the box and put them on the table, but not all of them. Then, Alice can do the same thing, but the amount of coins she puts on the table has to be no more then what Bob has taken in his last turn. Then, Bob does the same, and he can not take more coins then what Alice has taken in her last turn, etc. The winner is who takes the last coin (after the winner's last turn the box will be empty). Who has the winning strategy? (the answer can depend on the value of $n$). My guess is that Alice wins whenever $n=2^m$ and otherwise Bob wins (I checked $n=2,3,4,5,6,7,8,9,10$ and it seems to be true), but I am not sure how to prove it.

If $n$ is odd, Bob wins by taking $1$ coin in each of his turns.
If $n$ is not divisible by $4$ and $n>2$, Bob wins by taking $2$ in each of his turns (because Alice has to take $2$ as well, since if she takes $1$ we arrive at a position where there is an odd number of coins and It is Bob's turn).

Answer 1

As situation is determined by a pair $(n,m)$ of positive integers, where $n$ is the current numer of coins and $m$ the maximal allowed number to take.

• The starting position for Bob is $(n,n-1)$.

• In a position $(n,m)$ with $m\ge n$, the player can win immediately by taking $n$ coins

• Otherwise, the player can take $c$ coins, $1\le c\le m$, and the situation becomes $(n-c,c)$

Note that the only move valid from $(k,1)$ is by one coin to $(k-1,1)$. Consequently, $(k,1)$ is a winning position (W) if $k$ is odd and a losing position (L) if $k$ is even.

Claim. If $n$ is odd, then $(n,m)$ is W. If $n$ is even and $m>1$, then $(n,m)\sim (n/2,\lfloor m/2\rfloor)$. If $n$ is even and $m=1$, then $(n,m)$ is L.

Proof. By induction on $n$.

• If $n$ is odd, we can take $1$ coin and produce $(n-1,1)$ with $n-1$ even. By induction hypothesis, this is L so that $(n,m)$ is W.

• If $n$ is even and $m=1$, we must take $1$ coin and produce $(n-1,1)$ with $n-1$ odd. By induction hypothesis, this is W so that $(n,m)$ is L.

• If $n$ is even and $m>1$, then we can either take an odd number $c$ of coins (so enecessarily $c<n$), which results in $(n-c,c)$ with $n-c$ odd. By induction hypothesis, this is W. Or we can take an even number $c=2c'\ge 2$ of coins, which results in $(n-c,c)$, by induction hypothesis $\sim(\frac{n-c}2,\frac c2)=(\frac n2-c',c'),$. Our $(n,m)$ is W iff at least one of these successors is L. Equivalently, all corresponding $(\frac n2-c',c')$ with $1\le c'\le\lfloor \frac m2\rfloor$ are L. And this is equivalent to $(\frac n2,\lfloor \frac m2\rfloor)$ being W.

$\square$

Corollary. $(n,n-1)$ is L if $n$ is a power of $2$ and W otherwise.

Proof. If $n=2^k$ is a power of $2$ with $k\ge1$, then $(n,n-1)\sim(n/2^{k-1},\lfloor(n-1)/2^{k-1}\rfloor)=(2,1)$, which is L. If $n=2^ku$ with $u$ odd and $>1$, then $(n,n-1)\sim(n/2^k,\lfloor (n-1)/2^k\rfloor)=(u,u-1)$, which is W. $\square$

Answer 2

I'll prove your guess by induction.

"For $n$ coins, the 1st (2nd) person has winning strategy" means that no matter how many coins the 2nd (1st) person takes, if the 1st (2nd) person takes some number of coins in each step then he'll take the last coin.

Denote Bob and Alice as B and A resepctively. $n$ is the total number of coins.

Proof.

• Suppose $P(m)=\{2^i|i=1, 2,\dots, m\}$ where $m\geq1$.

• Initial Case. When $m=1$,

  for $n\in P(1)$, A has winning strategy.

• Induction Step. Suppose this claim $C$ is true:

  for $n \in P(m)$, A has winning strategy.

  Then for $$ \begin{align} n&=1+1+2+2^2+2^3+\dots+2^{m}\\ &=2^{m+1}, \end{align} $$ A has winning strategy:

  • Case 1. In the 1st step, B takes 1 coin. A will win.

  • Case 2. In the 1st step, B takes $b_1$ coins, where $$ \begin{align} b_1 &= 1+(1+2+2^2+2^3+\dots+2^k+r) \\ &= 2^{k+1}+r, \end{align} $$ where $$ \begin{gather} k\geq 0, \\ 0\leq r<2^{k+1}. \end{gather} $$ In 2nd step, B takes $a_2$ coins, where $$ a_2 = 2^{k+1}-r \leq 2^{k+1} \leq b_1. $$ Then there are left $$ s=2^{k+2}+2^{k+3}+\dots+2^{m} $$ coins. For $i=3, 5, 7,\dots$, $$ b_i\leq a_2 \leq 2^{k+1}. $$ For each term in $s$, i.e. $2^l$, B cannot take all coins of it, and A has strategy to take the last coin of it according to claim $C$.

  So

  for $n \in P(m+1)$, A has winning strategy

• I've proved that claim $C$ is true for $m\geq 1$.

• For $2^m< n < 2^{m+1}$, where $m\geq 1$, B has winning strategy:

  In 1st step, B takes $n-2^m$ coins and there are $2^m$ coins left. In 2nd step, A can take $l$ coins, where $l\leq n-2^m < 2^m$. From now on, regard A and B as the 1st and 2nd person respectively. According to claim $C$, the 2nd person, i.e. B, has winning strategy. $\square$