# Winning strategy in a number theory game

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?

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.
• 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. – Ingix Mar 31 '19 at 16:10
• @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 – Ross Millikan Mar 31 '19 at 16:37
• @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. – Ross Millikan Mar 31 '19 at 16:39
• 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. – Mark S. Apr 2 '19 at 10:12