Nim game variant

Question

Statment is as follow Given a number of piles in which each pile contains some numbers of stones/coins. In each turn, a player can choose only one pile and remove any number of stones (at least one) from that pile. The player who cannot move is considered to lose the game (i.e., one who take the last stone is the winner).

We can find solution by Xoring all the values of piles. But we have constraint In each turn, a player can choose only one pile and remove any number of stones between 1 to H. How to solve this modified one ?

From my point of view it will remain unchanged.. We have to calculated the xor values only.

Answer 1

We can use the theory of nim-values. Each pile has a nim-value and the value of the game is the nim-sum (XOR of the binary representations) of the nim-values of the piles. In this variant the nim-value of a pile is periodic with period $H+1$. The nim-value of a pile with $k$ stones, $0\le k\le H$ is $H$, and adding $H+1$ stones to a pile leaves its nim-value invariant.

As ever the game is a second player win iff its nim-value is zero.

Answer 2

It's quite changed. You have to compute the new Grundy value (see wikipedia or Google Grundy value combinatorial game, etc.) of each pile, which can be done recursively. If all piles have size $\le H$ then nothing changes....

Extreme case: $H=1$, then the piles are irrelevant and it's just odd vs even total values, which is quite different from normal nim.

Answer 3

Lork Shark the Unknown gave the correct answer, but I believe it's helpful to describe the strategy.

For a set o piles of sizes $p_1, p_2, \ldots, p_n$ respectively compute the residues $r_i = p_i \pmod{H+1}$ and pretend you're playing a regular Nim game with piles of size $r_i$. Now you are allowed to make any move you want, sinve $r_i \leqslant H$.

Suppose $r_1 \oplus r_2 \oplus \ldots \oplus r_n = 0$ and it's your opponents turn.

• If the opponent takes $k$ stones from pile $i$ with $k \leqslant r_i$, just play as you would in a regular Nim, so after your move $r_1 \oplus r_2 \oplus \ldots \oplus r_n = 0$ is still true.
• If the opponent takes $r_i < k \leqslant p_i$ stones from the pile $i$, take $H+1-k$ stones from the same pile so the imaginary situation is unchanged, therefore $r_1 \oplus r_2 \oplus \ldots \oplus r_n = 0$.

Thus you win.