# A game with stones and finding the winning set

For a positive integer $n$, two players $A$ and $B$ play the following game : Given a pile of $s$ stones, the players take turn alternatively with $A$ going first. On each turn the player is allowed to take either one stone, or a prime number of stones, or a positive multiple of $n$ many stones. The winner is the one who takes the last stone. Assuming both $A$ and $B$ play perfectly, for how many values of $s$ the player $A$ cannot win?

This is a problem from JBMO 2014. Can someone help me? I have not the slightest idea to do it. Thanks a lot.

## 1 Answer

Player $A$ cannot for exactly $n-1$ values of $s$. Why? If $s$ is a multiple of $n$ then $A$ can win immediately. Now notice there can be at most one losing position for $A$ in every congruence class. Since player $A$ can go from a number larger to the losing nosing number to the losing number by taking away a multiple of $n$. Now player $B$ is in a losing position and $A$ can win.

Is it possible for a non 0 congruence $i$ not to have a losing position?Suppose the losing position set is $p_1,p_2,p_3\dots p_j$. If there was no losing position in a given congruence that would mean from every value of $k$, we can reach one of the losing positions from $kn+i$, but that would mean there is always a prime of the form $(kn+i)-p_l$ however notice all of the $p$'s have different congruence mod $n$, then that would mean that for this to happen we would need to have a prime for every value of $k$, but this would imply the primes have a positive density. So there are exactly $n-1$ losing positions.

• Hi, can you please tell me about the part where you say "notice all the $p_i$'s have different congruence mod $n$, then that would mean we would need to have a prime for every value of $k$.....primes have a positive density". I can see that $kn+i=p_j$ is a prime for all $k$ but why does that imply the fact that density of primes is positive? Sorry for my ignorance. Thanks. – shadow10 Jun 25 '14 at 15:59
• Because for each $k$ we need a different prime. So the asymptotic density of the primes would be $\frac{1}{n}$. And we know the primes have density $0$ in the natural numbers. – Jorge Fernández Hidalgo Jun 25 '14 at 16:44
• OK I want to ask you how I am thinking just tell me if I am wrong. See we consider $|\mathbb{P}\cap \{1,2,..,kn\}|=k$. and hence the density is $\frac{k}{kn}=\frac{1}{n}$. Is this what you are saying? Sorry I don't know much about density. Thanks. – shadow10 Jun 25 '14 at 17:07
• yes, something like that. – Jorge Fernández Hidalgo Jun 25 '14 at 17:13
• Ok thanks a lot. Nice solution BTW! :) – shadow10 Jun 25 '14 at 17:16