# Winning strategy to a Nim-variant game

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?

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$$.