any ideas? Is this the exact statement of the problem? Should the answer be expressed in terms of n?

The answer's n-1, right? Sorry for double posting, my phone can't edit.

I'm not sure but I got the answer is \[ \left\lfloor\frac{n-1}{4}\right\rfloor \]??

No, it's n-1, i am sure

Itama wrote: 4. For a positive integer $n$, two payers $A$ and $B$ play the football game: Give 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 aprime number of stones, or a positive multiple of $n$ 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? The answer is $n-1$ Let $L$ be the set of losing positions ($A$ loses if $s \in L$). Clearly no element of $L$ is divisible by $n$. Let $x,y \in L$ and $x \equiv y (mod n)$, and suppose $x>y$. Then if $x=s$ there is a way for $A$ to win by taking a multiple of $n$ from $x$ so that $y$ stones remain which puts $B$ in a losing position, contradiction. therefore for two distinct $x,y\in L$ $x \not\equiv y(mod n)$ and it follows that the cardinal of $L$ is less or equal to $n-1$ Now if card $L < n-1$, let $a_1,a_2,...,a_t$ be the only elements of $L$ and $M\not\equiv0$ a residue mod n not found in $L$. By the Chinese remainder theorem there is a unique $X$ modulo $Pnp_1p_2...p_t$ for which $X \equiv M (n)$ $X \equiv a_i (p_i)$ for all i in 1,2..t $X \equiv 0 (P)$ Where the $p_i$ and $P$ are primes coprime with $n$ This shows that we can choose a very large $X$ for which -doesn't turn in a 0 or in a member of L by subtracting a multiple of $n$ -$X-a_i$ is a multiple of $p_i$ and $X$ gets arbitrarily large so $X-a_i$ cannot be prime -$P$ divides it so it isn't a prime Then $X \in L$ contradiction. So the answer is $n-1$

The answer is $n-1% $.Let's prove it: Lemma $1$:If $A$ loses for some $s_i$ then $A$ wins for every $s_j$ such that $s_i \equiv s_j (mod n)$: If $s_j>s_i$ then because they are congruent $mod$ $n$ $A$ can reduce $s_j$ to $s_i$ and then $B$ plays first and $B$ will lose.Else if $s_j<s_i$ then if $A$ would lose for that $s_j$ that would mean that $A$ would win for $s_i$ by analogy with the first case.Because of all that is written we proved this lemma. Lemma $2$:For numbers:$a_1 , a_2 , . . . , a_n-2$ such that they are all different $mod$ $n$ and none of them is divisible by $n$ ,there exist infinitely many numbers $k$ such that $k$ is not congruent to any of the given numbers and such that it is not congruent to $0 mod n$ and such that $k-a_i$ is not prime for any $1<=i<=n-2$.Proof: Let $X$ be any number that satisfies the congruention thing.Let $p_i=k-a_i$ for $1<=i<=n-2$.That means the differences are: $p_1 , p_2 , . . . , p_(n-2)$ .Now we observe $Y=X+ p_1 p_2 p_3 . . . p_(n-2)*n*z$.We see that for this $Y$ there is no prime difference so this lemma is proven too. Task: Because of lemma 1 we have that the maximum nubmer of s-es that $A$ will lose for is $n-1$.We will now prove that there are exatcly $n-1$ numbers and that all of those numbers are not congruent to each other or to $0$.It is obvious that if $n|s$ $A$ will win.Now we prove that for every remainder $mod$ $n$ there exists exactly one number congruent to that remainder that $A$ will lose for. Suposse that it is not like that.That means that for some $k$ for every $X \equiv k (mod n) A$ will win.Let $b_1 , b_2 , . . . , b_l$ be the numbers that $A$ will lose for.That means that if $A$ wins for some $s$ in the first move he must take certain number of stones such that the number of stones left is some of the numbers $b_1 , b_2 , . . . , b_l$. Now we choose our number $X$ by lemma 2 and such that none of the differences between $X$ and $b$ numbers is 1(it is possible because there are infinitely many numbers satisfying lemma 2).We see that he can't take any prime nubmer of stones because any of the differences is not prime and he also can't take $n*p$ because $B$ would win and he also can't take $1$ so we have that for such $X$ $B$ would win so we have a contradiction.So now we proved that the answer is : $n-1$ .

Let $s_{1},s_{2},\cdots ,s_{k}$ be all losing numbers for the first player in icreasing order. First let $k>n-1$, then since $s_{1},\cdots s_{k}$ are not divisible by $n$, there must exist $s_{i}$ and $s_{j}$ that are congruent modulo $n$, so, say $s_{i}<s_{j}$, then if $A$ took $s_{j}-s_{i}$ stones for case $s=s_{j}$, $B$ would lose and $A$ would win, contradiction. Now let $k<n-1$. If $n=2$ that would mean no losing numbers exist for $A$,but it is easy to check if $9$ is a losing number. So say $n>2$. Since $s_{1},s_{2},\cdots ,s_{k}$ none of them is divisible by $n$, there must exist $a$ (not divisible by $n$) such that none of them is congruent to $a$ modulo $n$ (otherwise there would be at least $n-1$ losing numbers). We can choose that $a$ such that $a>s_{k}+1$. Now consider $s=(un)!+a$ with $u$ being some positive integer satisfying $a<un$ Obviously that $s$ is not equal to some of losing numbers, so is a winning number. Suppose $A$ took first (to win) $\ell$ stones. Then $s=\ell$ or $s-\ell$ is a losing number i.e. $s-\ell=s_{i}$ for some $i$. $s\neq 1$, $s$ is not divisible by $n$ and since $1<a<un$ it is divisible by $a$ so is not a prime number. First case is impossible. For second case for some $i$ we have $s-s_{i}=(un)!+a-s_{i}=\ell$. Obviously $\ell$ is not divisible by $n$ and $\ell>1$. so $\ell$ is prime. But $1<a-s_{k}\le a-s_{i}\le a-s_{1}<a<un$ so $(un)!+1<\ell<(un)!+un$, a contradiction as we know that interval doesn't contain a prime number. In conclusion, $k=n-1$

This is a solution, which probably has been rephrased in more elementary fashion. But anyways. First see if $s\equiv 0\pmod n$ then $A$ wins immediately. Now we have two parts : $\bullet$ Part 1:There aren't two losing positions $s_1,s_2$ with $s_1\equiv s_2\pmod n$ Proof : If there was, then $s_1-s_2$ would be a multiple of $n$. Then $A$ would take that many stones and hence $B$ would be in $A$'s place and hence $s_2$ will become a losing position for $B$, and thus a winning position for $A$. Which is a contradiction. Hence number of losing positions for $A$ is $\le n-1$. $\bullet$ Part 2:There is a losing position in each nonzero residue class $\mod n$. Proof : Suppose for some $j\not\equiv 0\pmod n$ there is no losing position in the residue class containing $j$. Now suppose $\{\ell_1,\ell_2,\cdots,\ell_k\}$ are the set of losing positions of $A$. Then for $\{rn+j-\ell_i\}$ is a set of distinct primes as we vary $r$. Now this gives us a contradiction. Which finishes the problem since that will give number of losing positions for $A$ is $\ge n-1$. ( overkill alert) since this implies the set of primes $\mathbb{P}$ has density $>0$. Let $d_{\mathbb{P}}$ be the density of primes. Then $d_{\mathbb{P}}=\lim_{k\to \infty}\frac{|\mathbb{P}\cap \{1,2,\cdots ,k\}|}{k}$ Let $k=qn+s$. Now the limit becomes : \[ d_{\mathbb{P}}=\lim_{q\to \infty}\frac{|\mathbb{P}\cap \{1,2,\cdots, qn+s\}|}{qn+s}>0\] There are at least $r$ primes less than or equal to $rn+j-\ell_i$. Hence he limit becomes greater than $\frac{1}{n}$, better bounds are possible but right now nonzero density is good enough. And I have a proof for $d_{\mathbb{P}}=0$ as well since $d_{\mathbb{P}}=\lim_{n\to \infty}\frac{\pi(n)}{n}$ and the prime number theorem gives $\frac{\pi(n)}{n}\sim \frac{1}{\log n}$ thus $d_{\mathbb{P}}=0$. I suppose this leads to a contradiction, if it is correct ( ) anyways.

Answer $n-1$. Proof: If $A$ has a winning strategy then $n$ is good otherwise $n$ is bad. Clearly from each good number you can get to at least one bad number with a move and from each bad number you ca only move to good numbers. Clearly for each class mod $n$ there is at most $1$ bad number since otherwise you could move from a bad number to a bad number, absurd. For class $0$ all are good and $A$ wins immediately. For some class mod $n$ that isnt zero assume all numbers are good. Then from each number $s=xn+k$ for some $k$ you can go to one of the finitely many bad numbers $b_1,b_2,...,b_h$. But since all bad numbers arent from class $k$ you can go to a bad number by subtracting a prime or $1$. So at least one of the numbers $xn+k-b_i$ is a prime or $1$ for all $x$. But we know that we can choose arbitarly many consecutive composite numbers($m!+2,m!+3,...,m!+m$ for any $m$) so now we choose $n+max_{b_i}=d$ consecutive composite numbers $g+1,g+2,..,g+d$ and chose $x$ such that $g+d-n<xn+k\le g+d$. For this $x$ thanks to the choice of $d$ none of the numbers $xn+k-b_i$ are prime or $1$ and this is a contradiction. So every class mod $k$ that isnt zero has at most and at least one bad number so exactly $1$ bad number giving a total of $n-1$ bad numbers.

Take a look at this (easier) version of the problem from the Russian mathematical Olympiad 2011 for 11th grade - day 2 http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2262420&sid=8ba8d7c5c3f8b3f8145ae588e31fcc1b#p2262420 It's obvious that this Russian problem inspired the Romanian who proposed the problem above for the JBMO 2014. Alexandros

cretanman wrote: Take a look at this (easier) version of the problem from the Russian mathematical Olympiad 2011 for 11th grade - day 2 It's obvious that this Russian problem inspired the Romanian who proposed the problem above for the JBMO 2014. Yeah we can say tish is a generelization of those russian problem. For $s=r^2$, those is a special case of the this problem. Alexandros, Do you know who exactly proposed this question?

Marius Bocanu,a Romanian 12-grader,has silver on IMO 2013 proposed it.

Was he in IMO 2014?

This problem was really tough... I guess thats why it didnt selected for the JBMO

sttsmet wrote: This problem was really tough... I guess thats why it didnt selected for the JBMO Nope, actually it was selected and was quite deadly!

Here is the official solution to this very hard problem! Every multiple of $n$ is a winning position (one move is enough). Next, observe that if $a_i > a_j$ are two losing positions, then $n$ does not divide $a_i - a_j$ -- otherwise by subtracting $a_i - a_j$ stones from $a_i$, we would actually obtain that $a_j$ is a winning position, contradiction. In particular, there are at most $n-1$ losing positions. Conversely, we show that for each $1\leq r \leq n-1$ there exist a value $s\equiv r$ which is a losing position -- this would conclude that the answer is $n-1$. Suppose, for contradiction, that $mn+r$ is winning for all $m\geq 0$. Denote by $u$ the greatest losing position (write $u=0$ if there is no such) and set $s = $LCM$(2,3,\ldots,u+n+1)$. Note that all of $s+2$, $s+3$, $\ldots$, $s+u+n+1$ are composite. Let $m' \geq 0$ be such that $s+u+2 \leq m'n+r \leq s+u+n+1$. In order for $m'n+r$ to be winning, there must exist an integer $p$ which is $1$, a prime or a multiple of $n$, such that $m'n + r - p$ is losing (or $0$); in particular it must not exceed $u$. Since \[ s + 2 \leq m'n + r - u \leq p \leq m'n + r \leq s + u + n + 1\]the number $p$ cannot be $1$ or prime, hence it must be a multiple of $n$. If $p=qn$, then $m'n + r - p = (m'- q)n + r$ must be winning, contradiction.