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.

  • $\begingroup$ 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. $\endgroup$ – shadow10 Jun 25 '14 at 15:59
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Jun 25 '14 at 16:44
  • $\begingroup$ 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. $\endgroup$ – shadow10 Jun 25 '14 at 17:07
  • 1
    $\begingroup$ yes, something like that. $\endgroup$ – Jorge Fernández Hidalgo Jun 25 '14 at 17:13
  • $\begingroup$ Ok thanks a lot. Nice solution BTW! :) $\endgroup$ – shadow10 Jun 25 '14 at 17:16

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.