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 is one pile of $N$ stones. They take turns to pick stones from the pile, Alice will play first. In each turn, a player can only pick $k$ $(a \le k \le b)$ stones, the player who takes the last stone wins. With what property of $N$, will Alice win?

share|improve this question
1  
Well have you worked out a few simple examples to see what general pattern might hold? –  The Chaz 2.0 May 7 '13 at 2:18

2 Answers 2

For the game as described, Bob wins if $0 \le N \lt a$ as Alice cannot move. Alice wins if $a \le N \lt a+b$, as she can leave Bob something in the range $0$ through $a-1$. The pattern recurs modulo $a+b$, because whoever is winning can make sure two moves remove exactly $a+b$ stones. So Bob's winning positions are $0 \le N \pmod {a+b} \lt a$ and Alices are $a \le N \pmod {a+b} \le a+b-1$

share|improve this answer

For any given $a$ and $b$, the set of $N$ for which Alice wins is determined by some congruence conditions on $N$ - in other words, it's a periodic set (with some period depending on $a$ and $b$). For example, if $a=1$, then Alice can win if and only if $N$ is not a multiple of $b+1$. (Her strategy is to leave a multiple of $b+1$ stones for Bob every time he has to play.) This paper has some discussion and examples in more general situations.

share|improve this answer
    
Thank you for your answer and the paper link. –  shilk May 7 '13 at 2:26

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.