Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
1  
+1 for having worked on it and showing what you have done. You have made significant progress. A good problem, too. I wish I could do +more. I think your claim is not correct, as $(0,0,1)$ seems to be a first player win. I think there are some perturbations because zero is special. –  Ross Millikan Mar 31 at 4:16
    
@RossMillikan Yes you are right, the formula was wrong, actually in two different ways :/ I swapped win and loss and it is only true for $a,b,c>0$. I fixed it, thanks for pointing it out. –  Niklas B. Mar 31 at 4:23
    
(0,1,2) is a first player loss, as s/he must take one pile to zero, then the other player takes the other to zero. That isn't part of your claim, however. Zero is funny here. –  Ross Millikan Mar 31 at 4:30
    
@RossMillikan Yes, it seems like (a+1)⊕(b+1)⊕(c+1)=0 is the condition for loss, unless a=b=c=0, which is a loss too. (a+1)⊕(b+1)⊕(c+1) is not the grundy number though. –  Niklas B. Mar 31 at 4:38

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
That is an interesting way to look at it, thanks for your answer. I will look at this more closely tomorrow –  Niklas B. Mar 31 at 6:36
    
So the $+1$ is to ensure that valid moves in the original game never removes a pile in the transformed game? The more I think about it, the more I believe that the key observation here (that a winning move in NIM with unequal stacks never removes a pile) could have led one to the analogy with the $(a+1, b+1, c+1)$ NIM game. Maybe that's actually how other people solved it –  Niklas B. Apr 1 at 3:11

Not an answer, but too long for a comment: Even the two pile game is interesting. From $(0,a)$ the first player wins by moving to $(0,0)$ So a pile of $1$ is dead, and if there is one the first person can move to $(1,2)$ and win unless you are already there. Then $(2,n)$ is a first player win. It is looking like we should catalog the $P$ positions, where the second player wins. Again a pile of $3$ is dead because the other player can move to $(1,2)$. $(3,4)$ is $P$ because you must make a $1$ or $2$. I agree with your comment that $(n,n+1)$ with $n$ odd are the $P$ positions. If the difference is two or more the first player can attain that, so they are $N$ positions.
This drives the three pile game. If there are two piles of the form $(n,n+1)$ with $n$ odd the first player wins by taking the other pile to zero.

share|improve this answer
    
According to my analysis of the 2 pile case, $(n, n + 1)$ is a loss iif $n$ is odd, and $(10, 11)$ is a win because we can move to $(9, 10)$. The flaw here seems to be that $(2, 3)$ is in fact a win, not a loss, because you can move to $(1, 2)$ –  Niklas B. Mar 31 at 5:09
    
OK I agree, editing. –  Ross Millikan Mar 31 at 5:14
    
In fact I found that exactly the $(2k, 2k-1)$ cases are losses. You cannot get from one of them to another in one move. Every $(a,b)$ with $|a-b| > 1$ can be transformed into one of them in one move, so they are wins. $(2k, 2k+1)$ can also be transformed into $(2k, 2k-1)$ in one move, so those games are wins too. –  Niklas B. Mar 31 at 5:21
    
I agree. I have written up an explanation, but you are already there. –  Ross Millikan Mar 31 at 5:30
1  
@user11977 Actually $(6,7)$ is a win according to the logic here –  Niklas B. Mar 31 at 6:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.