Interesting Nim Variant - a new stone game

Question

this is from http://poj.org/problem?id=1740

Alice and Bob decide to play a new stone game.At the beginning of the game they pick n(1<=n<=10) piles of stones in a line. Alice and Bob move the stones in turn. At each step of the game,the player choose a pile,remove at least one stones,then freely move stones from this pile to any other pile that still has stones. For example:n=4 and the piles have (3,1,4,2) stones.If the player chose the first pile and remove one.Then it can reach the follow states.

2 1 4 2 
1 2 4 2（move one stone to Pile 2） 
1 1 5 2（move one stone to Pile 3） 
1 1 4 3（move one stone to Pile 4） 
0 2 5 2（move one stone to Pile 2 and another one to Pile 3） 
0 2 4 3（move one stone to Pile 2 and another one to Pile 4） 
0 1 5 3（move one stone to Pile 3 and another one to Pile 4） 
0 3 4 2（move two stones to Pile 2） 
0 1 6 2（move two stones to Pile 3） 
0 1 4 4（move two stones to Pile 4） 

Alice always moves first.

If there's no "moving stones from one pile to another" thing, given the initial condition, we could solve who's gonna win (Alice or Bob) using the grundy numbers. However, this additional condition, "each player can move stones freely from one pile to another after removing some stones," really complicates the problem.

The sample cases given were

1 1   -> Bob wins
2 1 3 -> Alice wins

However, I'm not sure how to come up with a general formula that would solve who would win when you're given the initial condition (numbers of stones in each pile).

Answer 1

This is not an answer, but since no one has offered anything better, I thought that it might be worthwhile to make a compilation of results for small numbers of piles. It’s complete for fewer than five piles and makes a start on the case of five piles.

• Clearly Alice wins when there is one pile by taking the whole pile.

• If there are two piles, with $m$ and $n$ stones respectively, Alice wins when $m\ne n$: she takes $|m-n|$ from the larger pile, and no matter what Bob then does, he must either leave her a single pile or two piles of unequal size.

• Alice wins when there are three piles. If two are equal in size, she takes all of the third pile. Otherwise, if the piles are of sizes $a<b<c$, she takes $c-(b-a)$ from $c$ and transfers $b-a$ to $a$, leaving Bob two piles of size $b$.

• Any initial position of the form $\langle m,m,n,n\rangle$, where $m,n>0$, is a win for Bob: if Alice takes a whole pile, Bob wins as first player from the resulting three-pile game, and if Alice does anything else, Bob can leave her another position of this type. It follows that any initial position of the form $\langle k,k,m,n\rangle$ with $0<k\le m<n$ is a win for Alice, since she can leave Bob a position of the first type. This leaves only positions of the form $\langle k,\ell,m,n\rangle$ with $0<k<\ell<m<n\rangle$. The simplest of these is $\langle 1,2,3,4\rangle$, which is a win for Alice, as she can leave $\langle 1,1,3,3\rangle$ by taking $2$ from the fourth pile and transferring one to the second pile. In general Alice can take $$n-(m-\ell)-k=(n-m)+(\ell-k)>0$$ from the fourth pile and transfer $m-\ell$ to the second, leaving $\langle k,k,m,m\rangle$, so Alice can win from these positions. In short, Alice wins unless the initial position is of the form $\langle m,m,n,n\rangle$ with $0<m\le n$.

• With five piles Alice wins if there are two piles of the same size by reducing the other three piles to a pair of piles of the same size. Thus, we need only consider the case in which all five piles are of different sizes. Bob will win if the initial position is $\langle 1,2,3,4,5\rangle$: Alice must leave him either four piles, or five piles, two of which are the same size. Otherwise, the player who first leaves the other player the position $\langle 1,2,3,4,5\rangle$ will win. This implies, for instance, that a five-pile position that differs from $\langle 1,2,3,4,5\rangle$ in exactly one position is a win for Alice: either it contains two piles of the same size, or she can reduce it to $\langle 1,2,3,4,5\rangle$.