As a first guess, I would say that the first plauer has a winning strategy iff $n$ is not $3\pmod 4$, but I'll have to check this out.

orl wrote: We say that a pile is a set of four or more nuts. Two persons play the following game. They start with one pile of $n \geq 4$ nuts. During a move a player takes one of the piles that they have and split it into two nonempty sets (these sets are not necessarily piles, they can contain arbitrary number of nuts). If the player cannot move, he loses. For which values of $n$ does the first player have a winning strategy? I think the first player has a winning strategy for all $n\neq 7$. However, it's the first game theory problem I have ever solved, so I can only hope my proof is correct... orl wrote: I see Christian Sattler participated. What about the other IMO2004 members who are still eligible for the Baltic Way contest ? Who determines the German team and how ? Actually, I believe the German participants must live in the north of Germany. However, currently Christian Sattler himself is trying to establish a plan that next year, 5 of the German IMO 2004 participants will go to Hamburg for the duration of the contest. Well, let's see. Darij

How about checking the case $n=11$ more carefully? If $A$ (the first player) breaks it into $1,10$ or $2,9$ or $3,8$, then $B$ wins. If he breaks it into $4,7$, then $B$ breaks $7$ into $3,4$, and he wins, and if $A$ breaks $11$ into $5,6$, then $B$ breaks $6$ into $1,5$, and it's not hard to see that he wins again after a few moves.

Yes, I analyzed $n=11$ too, but I couldn't move further, except following conjecture: if we initially have two piles $4k+1>4$ and $4l+2>4$ then first player wins. Is that true?

Sorry... so there was indeed a gap in my logics. Darij

Little correction to my conjecture: two piles of $4k+1$ and $4l+2$ nuts, and $4k+1<4l+2$; then first player wins.

Am I as blind as before right now, or does the game start with one pile? dg

Game starts with one pile. Actually, mentioned conjecture devoted to proof of grobber's conjecture that is $4k+3$ is only bad case for first player.

Indeed, I think we need something like Myth's conjecture in order to employ induction. The only clue I have is that the only bad cases for $A$ and $n\ge 14$ are $n=7,n=11$. I'd have to analyze $n=15$ next, but I'm a bit too lazy to do that .

In case $n=15$ we have to analyze situation after first move: 15 -> 5+10. Then second player makes 4, 5 and 6. And it is easy () to see that first player will lose.

If we show that $B$ has a winning strategy in the case $4k+3$, then the fact that $A$ has a winning strategy when $n\ne 4k+3$ follows easily. Actually, I think we could use the following inductive step, but I'm not sure it works (and I don't have a proof, or anything that looks like one ): If $n=4k+3$ and $A$ separates a $4$, then $B$ should break down that $4$, and leave $A$ with $4k-1$ as the first player, after which we could use the induction hypothesis. If $A$ separates a $1,2$ or $3$, then the inductive step is done, because $A$ leaves $B$ as the first player with a number $\not\equiv 3\pmod 4$, and since this number is $<4k+3$, we can use the induction hypothesis. The only case left, when $A$ splits the pile in to piles, both with $>4$ elements, I think (this is the thing which I haven't proved) $B$ should separate $4$ elements from one of the piles. Could this be true?

@Darij and others BTW is Christian also a math linker ? Hmm. Obviously Christian kills the Combinatorics problems, Darij the geometry ones. I don't know about Peter Scholze. Maybe number theory. The algebra problems could be a joint job. Regarding the participants. If Saint-Petersburg participates you also may have one half or one third of the Russian IMO team....

Finally, I have done it! We will prove by induction that positions $4k+3$, $(4k,4l)$, $(4k+1,4l+1)$ and $(4k+2,4l+2)$ are losing. As grobber said before, it is easy to derive that $4k$, $4k+1$ and $4k+2$ are winning positions if $4l+3$ are losing for all $l<k$. Suppose $A$ has position $4k+3$. There are two possibilities of dividing this pile: 1) $4k$, $4l+3$. Then $B$ makes $(4k-1,4l+3)$. 2) $4k+1$, $4l+2$. 2.1 If $k,l>0$ then $B$ makes position $(4k+1,4l+1)$ and wins. 2.2 If $k=0$, $l> 0$ then $B$ makes position $4l-1$ and wins. 2.3 If $k>0$, $l=0$ then $B$ makes position $4k-1$ and wins. Suppose $A$ has position $(4k+1,4l+1)$. Possible turns are 1) $4k$, $4m+1$, $4l+1$. 1.1 If $m=0$ then $B$ makes position $(4k,4l)$. 1.2 If $m>0$ then $B$ makes position $(4k-1,4m+1,4l+1)$ and wins. 2) $4k+2$, $4m+3$, $4l+1$. 2.1 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$. 2.2 If $k=0$, $m=0$ then $B$ makes $4l-1$. 2.3 if $k,m>0$ then $B$ makes $(4m+3,4k+1,4l+1)$. 2.4 If $k>0$, $m=0$ then $B$ makes $(4k+1,4l+1)$. Suppose $A$ has postion $(4k+2,4l+2)$. Possible turns are 1) $4k$, $4m+2$, $4l+2$. 1.1 If $m=0$ then $B$ makes $(4k,4l)$. 1.2 If $m>0$ then $B$ makes $(4k-1,4m+2,4l+2)$. 2) $4k+1$, $4m+1$, $4l+2$. 1.1 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$. 1.2 if $k,m>0$ then $B$ makes $(4k+1,4m+1,4l-1)$. Suppose $A$ has position $(4k,4l)$. Possibleturns are 1) $4k$, $4m$, $4l$. Then $B$ makes $(4k-1,4m,4l)$. 2) $4k+1$, $4m+3$, $4l$. 2.1 If $k>0$ then $B$ makes $(4k,4l,4m+3)$. 2.2 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$. 2.3 If $k=0$, $m=0$ then $B$ makes $(4l-1)$. 3) $4k+2$, $4m+2$, $4l$. 3.1 If $k=0$, $m>0$ then $B$ makes $(4m,4l)$. 3.3 If $k=m=0$ then $B$ makes $4l-1$. 3.3 If $k,m>0$ then $B$ makes $(4k+2,4m+2,4l-1)$. Hope it is correct

Call a set of piles a 'game'. If the player moving next in a game can win, the game is called 'winning' otherwise 'losing'. We have a clue observation: If set A is losing and set B is losing then the union of these two sets is also losing. This observation helps us proving by induction that if the set consists of two $piles$ containing the same number of nuts $mod$ $4$ then it's losing. Particularly this proves Myth's conjencture: B can move $4k+2,4l+1$ into the losing $4k+1,4l+1$. But Myth's conjencture proves that the losing piles are only those with $4k+3$ nuts. QED I think

Sorry, Myth, I opened this topic before you sent your solution, so I wrote the same solution as yours second time..

Actually, after some reading, I can see that this is elementary Sprague-Grundy theory. It should be easy to show by induction that the nim number corresponding to a game starting with a pile of $n$ elements is $0$ iff $n=4k+3$. Actually, starting from $n=4,5,6,7,8,9,10,11,\ldots$, the nim numbers are, I think, $1,2,3,0,1,2,3,0,\ldots$. Some more info can be found here, for example.