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.
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.