1
$\begingroup$

Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:

The games starts with 16 stones arranged as follow:

o (first pile)

ooo (second pile)

ooooo (third pile)

ooooooo (fourth pile)

Rules

1.Two players take turns to take away stones.

2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.

3.The player who takes away the last stone loses.

4.If one pile is split into two piles, you have to take away them in at least two turns.

For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)

o

ooo

ooxxo

ooooooo

Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:

First turn: oo xxo

Second turn: xxxx o

And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.

The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)? $\endgroup$ – Mark S. Dec 20 '18 at 17:04
  • $\begingroup$ There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim? $\endgroup$ – Mark S. Dec 20 '18 at 17:06
  • $\begingroup$ I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today $\endgroup$ – Learning Mathematics Dec 20 '18 at 23:47
  • $\begingroup$ You can learn about this stuff with things from this list of resources $\endgroup$ – Mark S. Dec 20 '18 at 23:50
  • $\begingroup$ One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn? $\endgroup$ – Mark S. Dec 21 '18 at 3:15
2
$\begingroup$

Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $\oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 \oplus 3 \oplus 5 \oplus 7 = 0$.

With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x \oplus y$.

However, it is easy to show that $x \oplus y \leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.

For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 \oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.

So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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