[Math] Nim Variant (Restricted removal)

combinatorial-game-theorygame theorypuzzle

Alice and Bob play the following game : There are $N$ piles of stones with $S_i$ stones in the $i$th pile. Piles are numbered from 1 to $N$. Alice and Bob play alternately, with Alice starting. In a turn, the player chooses any pile $i$ which has at least $i$ stones in it, and removes exactly $i$ stones from it. The game ends when there is no such pile. The player who plays last wins the game. Assuming Alice and Bob play optimally, who will win the game?

Best Answer

Your game with piles of $S_1,\ldots,S_N$ stones is identical to the Nim game with piles of $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$ stones. So you can pretend that you are playing Nim, and follow the usual Nim strategy.

For example, suppose we have piles $S_1 = 3, S_2 = 4, S_3 = 7$. We can pretend this is a Nim game with piles 3, 2, and 2, and play accordingly. In this case there are several winning Nim moves. One such is to take 1 stone from the third pile; this corresponds to taking 3 stones from $S_3$, moving to $(3, 4, 4)$.

Addendum Sorry, I misread the question and thought a legal move was to remove any multiple of $i$ stones from pile $S_i$. But the game as given is even simpler. Again we pretend that instead of $S_1,\ldots,S_N$ the piles contain $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$, and the rule is that a legal move removes one stone from any pile. It is now evident that a position is a win for the previous player if and only if $$\sum{\biggl\lfloor \frac{S_i}{i} \biggr\rfloor}$$

is even, and that it doesn't even matter what moves are made.