Let's play a game of NIM, but with a catch!
We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different.
We move in turns. In every move, we can select a pile and remove any number of stones from it. But there's a restriction: At no point during the game can we have two equally high piles of non-zero size. The player who cannot make a move loses.
- the game $(1, 3, 5)$ can be transformed into $(0, 3, 5)$, $(1, 2, 5)$, $(1, 0, 5)$, $(1, 3, 4)$, $(1, 3, 2)$ or $(1, 3, 0)$ in one move
- $(0, 1, 2)$ can be transformed into $(0, 0, 2)$ or $(0, 1, 0)$
- the game $(0, 0, 0)$ is an immediate loss
I happen to know a way to compute the outcome of such a game: Unless $a = b = c = 0$, the first player loses exactly if $(a+1) \oplus (b+1) \oplus (c+1) = 0$. $(0,0,0)$ is a loss too. I think it can be proven via induction on $a + b + c$.
What I don't know is how one would derive that result. I have puzzled over this quite some time and figured out a formula for the case with two piles, but could not generalize it. Then I looked up the solution. How would you approach this problem to get an intuition on what the winning or losing positions are? Or even better, is there some general method that often works for these types of games?
I know about the Sprague-Grundy theorem and P and N positions in general games on DAGs, so I can just use "brute force" to solve the problem, but unfortunately the numbers were too large to solve the problem that way and the results for smallish $a,b,c$ didn't really help me derive the formula. One important observation I can draw from this in hindsight however is that the value $(a+1) \oplus (b+1) \oplus (c+1)$ does not seem to be the grundy number of the game, they just happen to be zero for the same assignments of $a$, $b$ and $c$.
The source of the problem is the Andrew Stankevich Programming Contest 22, task D.
UPDATE: For the two pile case, exactly the positions $(2k, 2k - 1)$ are the losses. We can get from every other position to one of these or to $(0, 0)$, but we can't get from one of these into another of these. The base case is that $(1, 2)$ is a loss and $(0, a)$ is a win for $a > 0$.