How to reduce the following problem to Nim problem using Grundy numbers? The problem is similar the Nim problem except now for every non empty pile, either player can remove 0 items from that pile and have it count as their move; however, this move can only be performed once per pile by either player. Lets call this move as a zero move.
For example, let's say pile i initially has 2 items in it. If player A decides to use a Zero-Move on this pile , then neither A nor B can perform another Zero-Move on pile ; that said, either player is free to perform a Zero-Move on any other non-empty pile that hasn't had a Zero-Move performed on it yet.
How can I convert this problem to the standard nim problem using Grundy Numbers?
Is it solvable(telling which player will win) without using Grundy Numbers?
 A: The answer mentioned above is incorrect.It is clear that if pile size is zero no move is possible.g(0)=0
If  you try to build a solution bottom up  it turns out that if n is even the grundy number is n-1 and when it is odd the grundy is n+1.
Proof:
Grundy number of a state is the smallest positive integer that cannot be reached in one valid move.
When the pile size is zero the grundy number is 0 as no moves including the zero move is possible.
For a given pile size n we actually have two states:


*

*N is the size but no zero move is available.This is analogous to grundy number of the standard nim with grundy number equal to n.

*N is the size but zero move is available.Well,it turns out from this state you can reach the state mentioned above and all other states with a zero move remaining for size k < n.
Just try working your way bottom up.For n=1(with zero move left) you can reach n=1(no zero move left) and n=0(empty pile).Therefore,g(1)=2.For n=2 one cannot reach the state n=1(no zero move left) as both making a zero move and removing blocks simultaneously is not possible.g(2)=1.
