Junior Balkan Mathematical Olympiad

Denote by $k$ the sought number and let $\{s_1,s_2,\dots ,s_k\}$ be the corresponding values for $s$. We call each $s_i$ a losing number and every other nonnegative integer a winning number.

(I) Clearly every multiple of $n$ is a winning number. Suppose there are two different losing numbers $s_i>s_j$, which are congruent modulo $n$. Then, on his first turn of play, player $A$ may remove $s_i-s_j$ stones (since $n\mid s_i-s_j$), leaving a pile with $s_j$ stones for $B$. This is in contradiction with both $s_i$ and $s_j$ being losing numbers.

(II) Hence, there are at most $n-1$ losing numbers, i.e. $k\le n-1$. Suppose there exists an integer $r\in \{1,2,\dots ,n-1\}$, such that $mn+r$ is a winning number for every $m\in {\mathbb{N}}_0$. Let us denote by $u$ the greatest losing number (if $k>0$) or $0$ (if $k=0$), and let $s=\text{LCM}(2,3,\dots ,u+n+1)$. Note that all the numbers $s+2,s+3,\dots ,s+u+n+1$ are composite. Let $m^{\prime }\in {\mathbb{N}}_0$, be such that $s+u+2\le m^{\prime }n+r\le s+u+n+1$. In order for $m^{\prime }n+r$ to be a winning number, there must exist an integer $p$, which is either one, or prime, or a positive multiple of $n$, such that $m^{\prime }n+r-p$ is a losing number or $0$, and hence lesser than or equal to $u$. Since $s+2\le m^{\prime }n+r-u\le p\le m^{\prime }n+r\le s+u+n+1$, $p$ must be a composite, hence $p$ is a multiple of $n$ (say $p=qn$). But then $m^{\prime }n+r-p=(m^{\prime }-q)n+r$ must be a winning number, according to our assumption. This contradicts our assumption that all numbers $mn+r$, $m\in {\mathbb{N}}_0$ are winning.

(III) Hence, each nonzero residue class modulo $n$ contains a losing number.

(IV) There are exactly $n-1$ losing numbers (one for each residue $r\in \{1,2,\dots ,n-1\}$).

Similar proof of (III):

Lemma: No pair $(u,n)$ of positive integers satisfies the following property: () In $\mathbb{N}$ exists an arithmetic progression $(a_i{)}_{i=1}^{\infty }$ with difference $n$ such that each segment $[a_i-u,a_i+u]$ contains a prime.

Proof of the lemma: Suppose such a pair $(u,n)$ and a corresponding arithmetic progression $(a_i{)}_{i=1}^{\infty }$ exist. In $\mathbb{N}$ exist arbitrarily long patches of consecutive composites. Take such a patch $P$ of length $3un$. Then, at least one segment $[a_i-u,a_i+u]$ is fully contained in $P$, a contradiction.

Suppose such a nonzero residue class modulo $n$ exists (hence $n>1$). Let $u\in \mathbb{N}$ be greater than every losing number. Consider the members of the supposed residue class which are greater than $u$. They form an arithmetic progression with the property (), a contradiction (by the lemma).