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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .