0
$\begingroup$

Given the following variant to the game of Nim:

  • The game begins with n-heaps of m-stones each.
  • The player, every turn, must remove either k-stones from a heap if the number of stones in that heap is greater or equal to k, or as many stones as he desires from any non-zero heap. The turn is then over.
  • Only two players can play the game, p1 always starts, p2 after him.
  • The player who removes the last stone, loses.

What would be, if any, the winning strategy?

Personal thoughts:

Given a player p must remove k-stones first if possible, at some point, after each player has removed k-stones n-times we will be left with heaps with each less than k-stones, possibly even empty.

Example:

$h1$ has 5 stones, $h2$ has 4 and $h3$ has 7 ($<5, 4, 7>$); each player will remove 3 stones per turn:

  • p1 starts, removes 3 stones from $h1$: $<2, 4, 7>$
  • p2's turn, removes 3 stones from $h2$: $<2, 1, 7>$
  • p1's turn, removes 3 stones from $h3$: $<2, 1, 4>$
  • p2's turn, removes 3 stones from $h3$: $<2, 1, 1>$
  • p1's turn, removes 2 stones from $h1$: $<0, 1, 1>$
  • p2's turn, removes 1 stone, smelling victory, from $h2$: $<0, 0, 1>$
  • p1's turn, removes 1 stone from $h3$: $<0, 0, 0>$
  • p2 wins.

Given a situation in which the remaining heaps are, for example, $<4, 5, 6>$, and they may now remove how many stones they desire, what would be the optimal play for both of them?

$\endgroup$
3
$\begingroup$

Once all the heaps are below $k$ you are playing standard Nim and should use the usual strategy. In the $4,5,6$ case, the XOR of the three is $7$ and you should remove one stone from the $4$ heap, $3$ from the $5$ heap, or $5$ from the $6$ heap. For the whole game, you just count the parity of the number of $k$ moves that can be made because the order they are made doesn't matter. That tells you who goes first in the Nim game with all heaps less than $k$.

$\endgroup$

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.