3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ The first step is to program and see what happens in simple situations, say one pile, two piles and three piles. Then formulate a conjecture and prove it. In many cases the difficult part is formulating the conjecture. $\endgroup$ Oct 9, 2014 at 5:32
  • $\begingroup$ Alice can win from $\langle 2,1,3\rangle$, but not the way you said: she has to take $2$ from the $3$ pile and move the remaining stone to the $1$ pile to make $\langle 2,2,0\rangle$. Then no matter what Bob does, she either wins on her next turn or leaves him two singletons. $\endgroup$ Oct 9, 2014 at 5:52
  • $\begingroup$ Welcome back, @Brian. $\endgroup$ Oct 9, 2014 at 6:27
  • $\begingroup$ @BrianM.Scott thanks for pointing out the error. looks like making the numbers of stones equal is the key to this NIM... $\endgroup$
    – user98235
    Oct 9, 2014 at 6:53
  • $\begingroup$ You’re welcome. Yes, that’s the trick when there are two piles, just as in standard Nim; I’ve not had a chance to think seriously about what happens when there are more piles. $\endgroup$ Oct 9, 2014 at 6:56

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .