0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 21 '18 at 15:16
  • $\begingroup$ But can B split all the 3s in a single move? $\endgroup$ – saisanjeev Dec 23 '18 at 8:32
  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 23 '18 at 15:07
1
$\begingroup$

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

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