0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Well have you worked out a few simple examples to see what general pattern might hold? $\endgroup$ May 7, 2013 at 2:18

2 Answers 2

3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer and the paper link. $\endgroup$
    – shilk
    May 7, 2013 at 2:26
  • 1
    $\begingroup$ link is not working $\endgroup$
    – ankit
    Apr 12, 2020 at 22:03

You must log in to answer this question.

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