Two Player Strategy Game

Question

I have recently been struggling on a problem involving a modified game of Nim. I have tried finding an invariant or monovariant, but to no avail.

"In a game, Players X and Y take turns taking chips from a pile with P(at least 2) chips. Player X starts by taking at least one chip and at most P-1 chips. On each player's turn, they can take at least one chip but at most the amount the other player took on the previous turn. The player to take the last chip is the winner. What are all values of P such that Player Y has a winning strategy?"

Could anyone provide an answer with a rigorous proof? That would be very much appreciated!

Answer 1

Claim: Player $Y$ wins if and only if $P$ is a power of $2$.

Let $W(P)=X$ if $X$ wins the game with $P$ chips and $W(P)=Y$ if $Y$ wins, assuming that both players employ perfect strategy. Then:

• $W(2)=Y$, since $X$ must take $1$ chip and leave the last one for $Y$.
• $W(3)=X$, since $X$ can take $1$ chip and force $Y$ to leave the last chip for $X$.
• $W(P)=X$ for odd $P$, because $X$ can take $1$ chip at the beginning of the game and force each player to take only $1$ chip on each of their turns for the rest of the game, leaving $X$ with the last chip.

The case for even $P$ is interesting. If $X$ takes and odd number of chips, he ensures that he will lose (because he gives $Y$ an odd number of chips and the option to take only $1$, forcing a win for $Y$), and thus he must take an even number of chips. The same goes for $Y$, and so on. Thus, if both players use perfect strategy, each player always takes an even number of chips. So suppose we glue each pair of chips together, since each player always takes an even number. Then it reduces to the result of the game for $P/2$. Thus, we have $$W(P)=W(P/2), \space\text{even}\space P$$ Thus, by induction, it follows that $Y$ wins when $P$ is a power of $2$ and $X$ wins otherwise.

Awesome problem!