Serbian Mathematical Olympiad

Solution:

For $a, b \in \mathbb{N}$ let us define $\mathcal{L}\{a, b\} = \left\{ a x + b y \mid x, y \in \mathbb{N}_0 \right\}$. We shall first prove an auxiliary claim.

Lemma. Let $a > 1$ and $b > 1$ be coprime natural numbers.

(a) $N = a b - a - b$ is the largest natural number not in the set $\mathcal{L}\{a, b\}$.

(б) For every $z \in \mathbb{Z}$, $z \in \mathcal{L}\{a, b\}$ if and only if $N - z \notin \mathcal{L}\{a, b\}$.

Proof. (a) If $N = (b-1)a - b = a x + b y$ for some $x \in \{0, \ldots, b-1\}$ and $y \in \mathbb{Z}$, then $x \equiv b-1 \pmod{b}$, so $x \geqslant b-1$ and hence $y < 0$; therefore, $N \notin \mathcal{L}\{a, b\}$.

(б) It is clear that $z \in \mathcal{L}\{a, b\}$ implies $N-z \notin \mathcal{L}\{a, b\}$ (otherwise it would hold that $N = z + (N-z) \in \mathcal{L}\{a, b\}$). Let us now consider some $z \in \mathbb{Z} \setminus \mathcal{L}\{a, b\}$. If $x \in \{0, \ldots, b-1\}$ is such that $a x \equiv z \pmod{b}$, then $z < a x$, i.e., $a x - b y = z$ for some $y \in \mathbb{N}$. Then $N - x = (b-1-x)a + b(y-1) \in \mathcal{L}\{a, b\}$.

Let player A start the game by writing down a prime number $a \geqslant 5$, after which player B writes down a natural number $b$ such that $a \nmid b$. Only finitely many natural numbers do not belong to the set $\mathcal{L}\{a, b\}$, so the game is finite. Therefore, one of the players has a winning strategy.

Let us consider the game in which player A's second move is the number $N$. If that is a losing move, then B now has a winning response in the form of some allowed number $c$. However, then player A can, on the second move, instead of the number $N$, write down the number $c$, and thereafter follow the winning strategy of the other player. Indeed, by the lemma, the number $N-c$ is not allowed, so after the move $c$ the number $N = (N-c) + c$ is also not allowed, so B remains precisely in the position which would be losing for A.