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$.
Best Answer
This doesn't answer your question about how you may proceed with coming up with the conditions, but there is a cute way of proving it by comparing it to a game of regular Nim without induction as such.
The winning strategy for $a,b,c>0$ is to pretend you are playing a game of regular Nim with piles of size $a+1,b+1,c+1$ (where a 'move' is removing a fixed number of stones from a certain pile), and play to win.
If $(a+1)\oplus (b+1)\oplus (c+1) \neq 0$, then consider the winning move in Nim. This cannot be to remove an entire pile, since we know the other piles are unequal and thus not a losing position. Also, the winning move never leaves two equal sized piles and a nonzero third pile, as that is a losing position in Nim. Therefore this is a valid move to play.
Conversely, any move which is valid in the first game is always valid in the Nim game.
So the first player can ensure the Nim game is always valid, and thus by winning the Nim game cannot lose the original game.