Finding the winning strategy of a variation of the Nim game

Question

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?

Answer 1

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.