# How to give a winning strategy for this game?

I have the following question with me:

"Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who makes the last move wins. For what initial conditions does the first player win and what is his winning strategy"

I found this similar to Grundy's game but they haven't mentioned in the given question that the two piles are unequal. My book says that the first player wins if the largest number of chips in a pile is not equal to $$2^m - 1$$ for some $$m$$. The book further says that the required strategy for the first player is to split the piles in such a way that the one of the resulting piles should have the number of chips equal to $$2^m - 1$$ for some.

However, let's say I have $$(6,2,1)$$ to start with.

I perform the following operations $$(6,2,1) \rightarrow (3,3,2,1)$$This move is made by the first player. It is quite easy to see that B wins in any case in the above situation. Thus, followig the given strategy the statement given in the book seems to be wrong. Is there any mistake with the book or is there any mistake with my interpretation? A solution with the correct conditions would also be appreciated.

Thanks in advance

• The rule you quote is to split every pile greater than $1$, but in your example you did not split the $2$. Now $B$ must split both the $3$s to $2,1$ and $A$ splits the $2$s and wins. Dec 21 '18 at 15:16
• But can B split all the 3s in a single move? Dec 23 '18 at 8:32
• It is your game, but the third sentence in your quoted set of rules says that a player must split every pile larger than $1$. A game where a player splits just one pile would not be interesting because it doesn't matter what you do. If there are $n$ chips in $m$ piles the game will last $n-m$ moves and the winner just depends on the parity of that number. Dec 23 '18 at 15:07

## 2 Answers

The rule should be to leave a situation where the largest pile is $$2^m-1$$. You only care about the largest pile because all the others will be split to $$1$$ before this one. Now if the largest pile is $$2^m-1$$ at least one of the piles it is split into must be at least $$2^{m-1}$$ so you can leave $$2^{m-1}-1$$ and make sure all the other piles are smaller.

To contrast my strategy with the one you quote, say we start with one pile of $$8$$ chips. I claim the only winning move is to $$7,1$$, from which the first player can get to the largest pile being $$3$$ next move and win on the one after. Your writeup says leave a pile of $$2^m-1$$ so you could move to $$5,3$$. If I am the second player here, I move to $$3,2,2,1$$, you have to move to $$2,1,1,1,1,1,1$$ and I win by splitting the $$2$$.

At each move the number of piles increases by one. Suppose at the very beginning there are total $$N$$ coins and $$M$$ piles.

Finally there will be $$N$$ piles so $$N-M$$ moves were played. If $$N-M$$ is even player 2 wins if $$N-M$$ is odd player 1 wins. There is no specific strategy that $$P_1$$ needs he only needs to check $$N-M$$. Once he confirms $$N-M$$ is odd he can play blind.

• Thanks @Arctic Char. I am new here. So I don't know a lot off stuff. Nov 18 '21 at 15:35