Track / Stage 6 / 108 of 400 #1108 of 1964

Problem 1108

National Olympiad, first round

Number theory Difficulty 6.1 Find the answer

8.10 Starting from a given positive integer $n_{0}$ , two players, A and B, play a game of alternately choosing integers $n_{1}, n_{2}, \cdots$ according to the following rules: When $n_{2 k}$ is chosen, A can choose any integer $n_{2 k+1}$ such that $n_{2 k} \leqslant n_{2 k+1} \leqslant n_{2 k}^{2}$ ; When $n_{2 k+1}$ is chosen, B can choose $n_{2 k+2}$ , where $n_{2 k+2}$ is any integer such that $\frac{n_{2 k+1}}{n_{2 k+2}}$ is exactly a power of a prime number. It is agreed that A wins if he is the first to reach 1990, and B wins if he is the first to reach 1. Try to answer:
(1) For which $n_{0}$ does A have a winning strategy?
(2) For which $n_{0}$ does B have a winning strategy?
(3) For which $n_{0}$ do neither of them have a winning strategy?

The source for this one didn't record the answer, so there is nothing to check what you type against. Work it on paper and mark yourself against the solution below.

Official solution

[Solution] (1) Let $W$ be the set of all positive integers $n_{0}$ for which player A has a winning strategy. Since $45^{2}=2025>1990$ , we have
$\{45,46, \cdots, 1990\} \subset W .$

To further seek the elements of $W$ , we provide the following lemma.
Lemma Suppose $\{m, m+1, \cdots, 1990\} \subset W, N \ni s \leqslant 1990$ and $\frac{s}{p^{r}} \geqslant m$ , where $p^{r}$ is the largest prime power factor of $s$ . Then, if $\sqrt{s} \leqslant n_{0}1990$ , player A can choose a positive integer $r$ such that $2^{r} \cdot 3^{2}q^{s}$ . Then player B can choose
$n_{2}=q^{s}=\frac{n_{1}}{p^{r}}<\sqrt{n_{1}} \leqslant n_{0} .$

After a finite number of steps, it will inevitably be the case that $n_{2 k}=1$ , meaning that player B wins. Therefore, when $n_{0} \in\{1,2,3,4,5\}$ , player B has a winning strategy.
(3) For $n_{0} \in\{6,7\}$ , if player A chooses $n_{1}$ in the form (1), it will inevitably lead to a loss. Therefore, player A can only choose $n_{1}=30=2 \times 3 \times 5$ or $n_{1}=42=2 \times 3 \times 7$ . In this case, if player B chooses $n_{2}=10,15,14,21$ , it will lead to player A winning, so player B can only choose $n_{2}=6$ . Subsequently, the $n_{3}, n_{4}, n_{5}, n_{6}, \cdots$ chosen by player A and player B will be $30,6,30,6, \cdots$ . It is clear that for $n_{0} \in\{6,7\}$ , neither side has a winning strategy.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.