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' \in \mathbb{N}_0$, be such that $s + u + 2 \le m'n + r \le s + u + n + 1$. In order for $m'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'n + r - p$ is a losing number or $0$, and hence lesser than or equal to $u$. Since $s + 2 \le m'n + r - u \le p \le m'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'n + r - p = (m' - 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).