9.4. Given the set $S=\{1,2,3, \ldots, 2022\}$ and the set $A=\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{2022}\right\}$, which is a permutation of the set $S$. It is known that for any $1 \leqslant n, m \leqslant 2022$ the expression $a_{n}+a_{m}$ is divisible by the GCD $(n ; m)$. Find the number of possible sets $A$.
Solution. Let $n$ and $m$ be equal and equal to some odd number. Then $2 a_{n} \vdots \gcd(n ; n)=n$, which means $a_{n} \vdots n$. For $n \geqslant 1013$, this is only true if $a_{n}=n$ for $n=\{1013,1015, \ldots, 2021\}$. Let $n$ and $m$ be even. Then $a_{n}$ and $a_{m}$ must have the same parity, which means all numbers $a_{2}, a_{4}, \ldots, a_{2022}$ have the same parity, and all numbers $a_{1}, a_{3}, \ldots, a_{2021}$ have the other parity. In particular, it has already been proven that $a_{2021}$ is odd, so the numbers $a_{1}, a_{3}, \ldots, a_{2021}$ are odd, and the numbers $a_{2}, a_{4}, \ldots, a_{2022}$ are even. Take the maximum odd number $k$ for which $a_{k}$ is not yet defined. By the proven fact, $a_{k} \vdots k$, and all odd numbers greater than $k$ are already defined, so $a_{k}=k$. Continuing this process, we get $a_{k}=k$ for all odd $k$. Now we need to solve the problem for the numbers $a_{2}, a_{4}, \ldots, a_{2022}$, which coincide with the set of numbers $2,4, \ldots, 2022$. Let $a_{2 n}=2 b_{n}$ and $a_{2 m}=2 b_{m}$, where $1 \leqslant n, m, b_{n}, b_{m} \leqslant 1011$. Then $a_{2 n}+a_{2 m}=2\left(b_{n}+b_{m}\right) \vdots \gcd(2 n ; 2 m)=$ $2 \gcd(n ; m)$. This means that for any $1 \leqslant n, m, b_{n}, b_{m} \leqslant 1011$, $b_{n}+b_{m} \vdots \gcd(n ; m)$. We have reduced the problem to an analogous one but for the set of numbers $\{1,2,3, \ldots, 1011\}$. Repeating similar reasoning, we get that $b_{k}=k$ for all odd $k$, so $a_{2 k}=2 k$ for all odd $k$. Now we need to determine the numbers $a_{k}$ with indices that are multiples of four. Repeating the process multiple times, we will reach a situation where the set of numbers $\{1,2\}$ remains, and it corresponds to numbers $2^{p}$ and $2^{p-1}$ such that $2^{p} \leqslant 2022<2^{p+1}$, that is, to the numbers $a_{512}$ and $a_{1024}$.

Case 1. $a_{512}=512, a_{1024}=1024$. In this case, $a_{n}=n$ for all $1 \leqslant n \leqslant 2022$. The condition of the problem is satisfied, since if $\gcd(n ; m)=d$, then $n=d x, m=d y$ and $a_{n}+a_{m}=n+m=d(x+y) \vdots \gcd(n ; m)=d$.

Case 2. $a_{512}=1024, a_{1024}=512$. For all pairs $n, m$, not equal to 512 and 1024, and for $n=512, m=1024$, the condition has been verified in the previous case. In all other cases, either $a_{n}+512=n+512 \vdots \gcd(n ; 1024)$, which is true since $\gcd(n ; 1024) \leqslant 512$, or $a_{n}+1024=n+1024 \vdots \gcd(n ; 512)$, which is true since 1024 is a multiple of 512.

Both sets of numbers are valid.

Answer. Two sets.