3
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ Who wins when P=2,3,4,5? Start by making small examples. $\endgroup$
    – saulspatz
    Mar 19, 2018 at 23:32
  • $\begingroup$ Game sounds weird. If the first player takes one chip, then each player will remove one chip at a time. If P is odd the first player wins. If P is even the second player wins, since if the first player removes P-1 chips, he loses also. $\endgroup$ Mar 19, 2018 at 23:39
  • $\begingroup$ @herbsteinberg The proof that $Y$ wins for even $P$ is going to take a little bit more work than that... $\endgroup$ Mar 19, 2018 at 23:40
  • 1
    $\begingroup$ @herbsteinberg When $P=2$ the first player loses. Also when $P=4.$ When $P=6$ however, he takes $2$ chips and wins. $\endgroup$
    – saulspatz
    Mar 19, 2018 at 23:45

1 Answer 1

4
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ It would be nice to see the Sprague-Grundy numbers for the positions. $\endgroup$ Mar 19, 2018 at 23:50
  • $\begingroup$ @EthanBolker Good lord, I have no idea what those are. Time to consult Wikipedia! XD $\endgroup$ Mar 19, 2018 at 23:51
  • $\begingroup$ Wikipedia will get you started. Then see section 3.2 in cs.umb.edu/~eb/320/FergusonGames.pdf $\endgroup$ Mar 20, 2018 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy