Track / Stage 6 / 83 of 400 #1083 of 1964

Problem 1083

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?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

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 and solution reproduced as published; topic, difficulty and ordering added by this site.