Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Alice and Bob play the following game : There are $N$ piles of stones with $S_i$ stones in the $i$th pile. Piles are numbered from 1 to $N$. Alice and Bob play alternately, with Alice starting. In a turn, the player chooses any pile $i$ which has at least $i$ stones in it, and removes exactly $i$ stones from it. The game ends when there is no such pile. The player who plays last wins the game. Assuming Alice and Bob play optimally, who will win the game?

share|improve this question
    
Pls upvote/accept answers if you consider them satisfactory. math.stackexchange.com/faq#howtoask –  leonbloy Oct 2 '12 at 21:26

1 Answer 1

up vote 2 down vote accepted

Your game with piles of $S_1,\ldots,S_N$ stones is identical to the Nim game with piles of $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$ stones. So you can pretend that you are playing Nim, and follow the usual Nim strategy.

For example, suppose we have piles $S_1 = 3, S_2 = 4, S_3 = 7$. We can pretend this is a Nim game with piles 3, 2, and 2, and play accordingly. In this case there are several winning Nim moves. One such is to take 1 stone from the third pile; this corresponds to taking 3 stones from $S_3$, moving to $(3, 4, 4)$.

Addendum Sorry, I misread the question and thought a legal move was to remove any multiple of $i$ stones from pile $S_i$. But the game as given is even simpler. Again we pretend that instead of $S_1,\ldots,S_N$ the piles contain $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$, and the rule is that a legal move removes one stone from any pile. It is now evident that a position is a win for the previous player if and only if $$\sum{\biggl\lfloor \frac{S_i}{i} \biggr\rfloor}$$

is even, and that it doesn't even matter what moves are made.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.