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$
  • $\begingroup$ Who wins when P=2,3,4,5? Start by making small examples. $\endgroup$ – saulspatz Mar 19 '18 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$ – herb steinberg Mar 19 '18 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$ – Frpzzd Mar 19 '18 at 23:40
  • $\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 '18 at 23:45
3
$\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$
  • $\begingroup$ It would be nice to see the Sprague-Grundy numbers for the positions. $\endgroup$ – Ethan Bolker Mar 19 '18 at 23:50
  • $\begingroup$ @EthanBolker Good lord, I have no idea what those are. Time to consult Wikipedia! XD $\endgroup$ – Frpzzd Mar 19 '18 at 23:51
  • $\begingroup$ Wikipedia will get you started. Then see section 3.2 in cs.umb.edu/~eb/320/FergusonGames.pdf $\endgroup$ – Ethan Bolker Mar 20 '18 at 0:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.