2023 Chinese IMO National Team Selection Test

Let $x(n)={\sum }_{v_p(n)\ge 2}1$ and $y(n)={\sum }_{v_p(n)=1}1$. Let the maximum number of islands that can be visited be denoted as $k(n)$. Then we have: $$k(n)=\{\begin{array}{ll}3x(n)+2y(n)+1,& v_2(n)\ne 1,\\ 3x(n)+2y(n),& v_2(n)=1.\end{array}$$ For $x,y\in \mathbb{Z}$ and $m\in {\mathbb{Z}}_{>0}$, if $xy\equiv xa(\mathrm{mod}m)$, we denote this as $x\to y(\mathrm{mod}m)$. Let $p$ be a prime factor of $n$ and $p^{\alpha }\nmid n$. For a sequence $x_1\to x_2\to \cdots \to x_k(\mathrm{mod}n)$, the same relation holds modulo $p^{\alpha }$: $$x_1\to x_2\to \cdots \to x_k(\mathrm{mod}{p}^{\alpha }).$$ (1) If $x_i\ne 0(\mathrm{mod}{p}^{\alpha })$, then $x_{i+1}$ is coprime to $p$. This is because $p^{\alpha }\mid x_i(x_{i+1}-a)$, and $p^{\alpha }\nmid x_i$. Therefore, $p\mid x_{i+1}-a$. Since $a$ is coprime to $n$, we have $p\nmid a$, which implies $p\nmid x_{i+1}$. (2) If $x_i$ is coprime to $p$, then $x_{i+1}\equiv a(\mathrm{mod}{p}^{\alpha })$. This is because $p^{\alpha }\mid x_i(x_{i+1}-a)$, and since $p\nmid x_i$, we have $p^{\alpha }\mid x_{i+1}-a$. (3) From (1) and (2), we can conclude that if $\alpha \ge 2$, the sequence $x_1,x_2,\dots ,x_k(\mathrm{mod}{p}^{\alpha })$ undergoes at most three changes: it changes from being divisible by $p^{\alpha }$ to being nonzero, then becomes coprime to $p$, and finally becomes congruent to $a$ modulo $p^{\alpha }$. If $\alpha =1$ and $p\ne 2$, then $x_1,x_2,\dots ,x_k(\mathrm{mod}{p}^{\alpha })$ undergo at most two changes: it changes from being congruent to 0 modulo $p$ to being coprime to $p$, and finally becomes congruent to $a$ modulo $p$. If $\alpha =1$ and $p=2$, then $x_1,x_2,\dots ,x_k(\mathrm{mod}{p}^{\alpha })$ undergo at most one change: it changes from being congruent to 0 modulo 2 to being congruent to $a$ modulo 2. Assuming that $x_1,x_2,\dots ,x_k(\mathrm{mod}n)$ have distinct adjacent terms, then adjacent terms have changes in some modulo $p^{\alpha }$, implying that $k\le k(n)$. (4) Construct examples for $k=k(n)$. First, consider the cases based on modulo $p^{\alpha }$. (i) If $\alpha \ge 2$, we have $0\to p\to a+p^{\alpha -1}\to a(\mathrm{mod}{p}^{\alpha })$. (ii) If $\alpha =1$ and $p\ne 2$, we have $0\to b\to a(\mathrm{mod}p)$, where $b$ is coprime to $p$ and $b\ne a(\mathrm{mod}p)$. (iii) If $\alpha =1$ and $p=2$, we have $0\to a(\mathrm{mod}2)$. Let $n=p_1^{{\alpha }_1}\cdots p_w^{{\alpha }_w}$ be the prime factorization of $n$. For each $p_i^{{\alpha }_i}$, we choose a sequence corresponding to the three cases mentioned above. Note that $0\to 0$ and $a\to a$. We can appropriately add some zeros at the beginning and some $a$'s at the end of the sequences to ensure that their lengths reach $k(n)$. Let's denote these modified sequences as $L_i$. It is required that for $p_i^{{\alpha }_i}$ and $p_j^{{\alpha }_j}$ ($i\ne j$), the positions where changes occur in $L_i$ and $L_j$ are different.

For example, suppose ${\alpha }_1\ge 2$, we can take $$L_1:0\to p_1\to a+p_1^{{\alpha }_1-1}\to a\to a\to \cdots \to a(\mathrm{mod}{p}_1^{{\alpha }_1}).$$ If ${\alpha }_2=1$ and $p_2\ne 2$, we can also take $$L_2:0\to 0\to 0\to 0\to b\to a\to a\to \cdots \to a(\mathrm{mod}{p}_2),$$ and continue this way to construct $L_3,\dots ,L_w$. By using the $t$-th term of $L_1,L_2,\dots ,L_w$ and the Chinese Remainder Theorem, we can determine $x_t$. Since $x_t\to x_{t+1}(\mathrm{mod}{p}_i^{{\alpha }_i})$ for $1\le i\le w$, it follows that $x_t\to x_{t+1}(\mathrm{mod}n)$. Moreover, the sequence $x_1,x_2,\dots ,x_{k(n)}$ modulo $n$ has distinct terms. This confirms the conclusion of the original problem, and the maximum value $k(n)$ is given by the formula mentioned at the beginning of the solution. $\square$