1
$\begingroup$

Two people play a game, lets call them A and B. There are $n$ stones on a table and players start to remove them. They can remove $p-1$ stones at once where $p$ is a prime number. Whoever takes the last stone, wins. Show that if player A starts then player B has a winning strategy for infinite number of $n$.

My thoughts so far:

It seems that whoever can take stones such that 3 stones remain will win. I haven't figured out when it is impossible for player A to do so. Player B needs to avoid a position where there are $p+2$ stones remaining. Any ideas on how to go about this?

$\endgroup$

1 Answer 1

2
$\begingroup$

Assume $B$ can only win finitely many starting positions. We know there is at least one, which is $3$. There is a largest one, call it $N$. Now consider the starting position $(N+1)!+N$. There are no primes in the range $[(N+1)!+2,(N+1)!+N+1]$, so $A$ must leave a position larger than $N$. We assumed all numbers larger than $N$ were wins for the first player, so $B$ can use the first player strategy and win. This violates our assumption that $N$ was the largest second player win.

$\endgroup$
5
  • 1
    $\begingroup$ I would suggest adding that $3$ is an obvious starting postiton where $B$ wins (as OP implied). Because if there was no starting position where $B$ wins, your argument breaks down. $\endgroup$
    – Ingix
    Mar 31, 2019 at 16:10
  • $\begingroup$ Wouldn't we have to prove that for arbitrary n there exists a winning strategy for either player or it is safe to assume there is? $\endgroup$ Mar 31, 2019 at 16:21
  • $\begingroup$ @MarkusPunnar: We have to show the game terminates and does not draw, but the fact that one can take $1$ is enough for that. Then the usual Sprague-Grundy theory applies. Every position is either $P$, a win for the previous player or $N$, a win for the next player. An $N$ position is one that can reach a $P$ position, a $P$ position is one that can only reach $N$ positions. We are asked to prove there are infinitely many $P$ positions $\endgroup$ Mar 31, 2019 at 16:37
  • $\begingroup$ @MarkusPunnar: this kind of strategy stealing argument is fairly common. Note I have given $B$ no indication how to find a winning strategy, I have just shown that one exists. $\endgroup$ Mar 31, 2019 at 16:39
  • $\begingroup$ As an aside, I imagine the $P$ and $N$ stuff (though probably not the notation) predates "the usual Sprague-Grundy theory". The idea is basically a proof of Zermelo's theorem. $\endgroup$
    – Mark S.
    Apr 2, 2019 at 10:12

You must log in to answer this question.

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