Given the following variant to the game of Nim:
- The game begins with
- 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,
- The player who removes the last stone, loses.
What would be, if any, the winning strategy?
Given a player
p must remove
k-stones first if possible, at some point, after each player has removed
n-times we will be left with heaps with each less than
k-stones, possibly even empty.
$h1$ has 5 stones, $h2$ has 4 and $h3$ has 7 ($<5, 4, 7>$); each player will remove 3 stones per turn:
p1starts, 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>$
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?