0
$\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$
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$
  • 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 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$ – Markus Punnar Mar 31 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$ – Ross Millikan Mar 31 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$ – Ross Millikan Mar 31 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 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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