Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|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 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. –  Bananarama Jun 25 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 at 17:07
1  
yes, something like that. –  Bananarama Jun 25 at 17:13
    
Ok thanks a lot. Nice solution BTW! :) –  shadow10 Jun 25 at 17:16
add comment

Your Answer

 
discard

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.