Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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. – Carry on Smiling 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. – Carry on Smiling Jun 25 '14 at 17:13
Ok thanks a lot. Nice solution BTW! :) – shadow10 Jun 25 '14 at 17:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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