grundy's game dividing a pile into two unequal

问题:

I have come across a problem.

There are N piles of stones where the ith pile has xi stones in it. Alice and Bob play the following game:

a. Alice starts, and they alternate turns.

b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Most important statement-"The answer should be Alice if Alice wins else the answer is Bob."

Now my question is that if we have only one pile of 8 stones initially, the actual answer is Bob. But as far as I think, if Alice breaks the initial set of 8 stones into two piles of 7 and 1 ie, 8->7+1 then there is not way that Bob could win if Alice plays with best strategy(optimally). Yet the answer is Bob. Can someone help me out to find out why the answer is Bob? I think the statement which I have marked as most important above matters a lot in this answer but I am not able to figure it out yet. Can anyone help? You can refer to this link which shows the exactly same illustration on Wikipedia of "Grundy's Game"

Any elementary idea is also appreciated.

---

Guys this is the exact problem I am facing. Any small idea is also appreciated.

Grundy's game extended to more than two heaps

回答1:

If Alice goes first, none of the moves available to her will allow her to win. Proof by exhaustion:

If Alice divides the stones into 5,2,1, then Bob wins in the following way:

1. Bob's turn. 5,2,1 -> 4,2,1,1
2. Alice's turn. Her only legal move is to divide the four. 4,2,1,1 -> 3,2,1,1,1
3. Bob's turn. 3,2,1,1,1 -> 2,2,1,1,1,1
4. Alice's turn. No moves are available. Alice loses.

If Alice divides the stones into 4,3,1, then Bob wins in the following way:

1. Bob's turn. 4,3,1 -> 3,3,1,1
2. Alice's turn. Her only legal move is to divide a three. 3,3,1,1 -> 3,2,1,1,1
3. Bob's turn. 3,2,1,1,1 -> 2,2,1,1,1,1
4. Alice's turn. No moves are available. Alice loses.

If Alice divides the stones into 7,1, then Bob wins in the following way:

1. Bob's turn. 7,1 -> 4,2,1,1 (Note that this move is impossible under Wikipedia's "divide only into two piles" rule, but not under the OP's "divide into any number of piles" rule.)
2. Alice's turn. Her only legal move is to divide the four. 4,2,1,1 -> 3,2,1,1,1
3. Bob's turn. 3,2,1,1,1 -> 2,2,1,1,1,1
4. Alice's turn. No moves are available. Alice loses.

If Alice divides the stones into 6,2, then Bob wins in the following way:

1. Bob's turn. 6,2 -> 4,2,2
2. Alice's turn. Her only legal move is to divide the four. 4,2,2 -> 3,2,2,1
3. Bob's turn. 3,2,2,1 -> 2,2,2,1,1
4. Alice's turn. No moves are available. Alice loses.

If Alice divides the stones into 5,3, then Bob wins in the following way:

1. Bob's turn. 5,3 -> 3,3,2
2. Alice's turn. Her only legal move is to divide a three. 3,3,2 -> 3,2,2,1
3. Bob's turn. 3,2,2,1 -> 2,2,2,1,1
4. Alice's turn. No moves are available. Alice loses.

回答2:

I dont see any way in which Bob can win this if Alice plays optimally. wikipedia explains it properly. If both the players play optimally and if 8 is initial number of stones then Alice should win. Because after 1 complete-round(both takes 1 turn each) Alice can always enforce Bob with configuration 4+2+1+1. From this configuration all Bob can do is 3+1+2+1+1 Hence Alice wins