XXIX Rioplatense Mathematical Olympiad

The answer is $13$.

There is an $m_0\in \{1,2,\dots ,2021\}$ such that $a_{m_0}=2022$, $m_0$ being a divisor of $2022$.

If $m_0=1$, we have $a_1=2022$. In this case, we must have $a_k=k$, for all $k=2,3,\dots ,2021$. Indeed, for a given $k\in \{2,3,\dots ,2021\}$, suppose that $a_{n_0}=k$, with $n_0\ne k$. So, as $n_0|a_{n_0}=k$, we are left with $n_0|k$ and therefore $n_0<k\le 2021$. Now, let $n_1$ be such that $a_{n_1}=n_0$. We have $n_1|n_0$, but now $n_1\ne n_0$, because if $n_1=n_0$, we are left with $a_{n_1}=a_{n_0}$ from which $n_0=k$ (Absurd). So, $n_1<n_0$. And so on. We will have a sequence $2021>n_0>n_1>\cdots >n_p=1$ such that $a_{n_j}=n_{j-1}$ and $n_j|n_{j-1}$, for all $j=1,2,\dots ,p$. But in this case, $a_{n_p}=a_1=2022$ and therefore $n_{p-1}=2022$, which is a contradiction. Therefore, the permutation $(2022,2,3,\dots ,2021)$ is the only solution in this case.

If $m_0\ne 1$, consider the sequence $m_0>m_1>\cdots >m_p=1$ such that $a_{m_j}=m_{j-1}$ and such that $m_j|m_{j-1}$, for all $j=1,2,\dots ,p$. Note that the sequence $1=m_p,m_{p-1},\dots ,m_0,2022$ is a chain of divisors of $2022$ such that each term is a divisor of the next. From what was previously exposed, any number $k\notin \{m_0,m_1,\dots ,m_p\}$ must satisfy $a_k=k$.

Therefore, the number of permutations is equal to the number of such chains. Since $2022=2\cdot 3\cdot 337$, its set of divisors is $\{1,2,3,6,337,674,1011,2022\}$, so the possible strings will be: $$(1,2022),(1,2,2022),(1,3,2022),(1,6,2022),(1,337,2022),(1,674,2022),(1,1011,2022),(1,2,6,2022),(1,2,674,2022),(1,3,6,2022),(1,3,1011,2022),(1,337,674,2022)\text{ and }(1,337,1011,2022).$$ In total, we will have $13$ permutations, one for each string. So, for example, for the string $(1,2,6,2022)$, it means that $a_1=2$, $a_2=6$, $a_6=2022$ and $a_k=k$, for $k\ne 1,2,6$.