Two players, $A$ and $B,$ alternatively take stones from a pile of $n \geq 2$ stones. $A$ plays first and in his first move he must take at least one stone and at most $n-1$ stones. Then each player must take at least one stone and at most as many stones as his opponent took in the previous move. The player who takes the last stone wins. Which player has a winning strategy?
Problem
Source:
Tags: combinatorics
tenniskidperson3
31.05.2015 02:34
If $n$ is a power of $2$, then $B$ wins. Otherwise, $A$ wins. A position is a winning position if and only if the highest number of stones your opponent last took, the number you may take this turn, is at least as many as the highest power of $2$ dividing your number. (For example, having an odd number of stones is always a winning position, because you may always take at least one stone; and only if your opponent just took 1 stone can being at $6$ be a losing position.)
The winning strategy is to remove enough stones to leave a number of stones divisible by $2$ more times than any number between it and the number you started with. For example, if your opponent had $13$ and removed $6$ to give $7$, a winning move is to take away either $1$ or $3$ to get to $6$ or $4$. If you're at a winning position, you can always do this: suppose you're at $m=2^k\ell$ and you are allowed to take $j\geq2^k$, then you take $2^k$ stones to leave you at $m-j=2^k(\ell-1)$ which has a higher power of $2$ than $m$ does. On the other hand, if you're at a $m=2^k\ell$ and you are only allowed to take $j<2^k$, then you cannot raise the power of $2$ by taking away stones. The positions you can win from are if you have $n$ stones left and you are allowed to take $n$ or more; this is certainly a winning position, since no power of $2$ dividing $n$ can be bigger than $n$ itself.