IMO TST Day 1

Claim 0 $f$ is bijective.
Proof. First, it is easy to see that $f$ is surjective, since for any given $x \in \mathbb{N}$, $f^{n-1}(x)$ exists and $f(f^{n-1}(x)) = x$. Now, assume $f(x) = f(y)$. Choose $m = x^{2023}$ and $n = y^{2023}$. Thus, $f^m(x) = x$ and $f^n(y) = y$, and note that
$$\begin{align*} f(x) = f(y) &\implies f^{mn-1}(f(x)) = f^{mn-1}(f(y)) \\ &\implies (f^m)^n(x) = (f^n)^m(y) \\ &\implies x = y \end{align*}$$
Hence, $f$ is injective, and therefore, $f$ is bijective too.

Claim 1 $f^a(x) = f^b(x) = x \implies f^{\gcd(a,b)}(x) = x$.
Proof. Let $d$ be the smallest positive integer such that $f^d(x) = x$. By Euclidean algorithm, $d \mid a$ and $d \mid b$. Therefore $d \mid \gcd(a, b)$, and so $f^{\gcd(a,b)}(x) = x$. $\square$

Claim 3 For every $x, y, n \in \mathbb{N}$, $x | y \implies f^n(x) | f^n(y)$
Proof. This follows by using the second condition repeatedly. $\square$

Claim 4 For every $x, y \in \mathbb{N}$, $x | y \Longleftrightarrow f(x) | f(y)$.
Proof. It suffices to prove $f(x) | f(y) \implies x | y$. To this end, suppose $f^m(x) = x$ and $f^n(y) = y$. Using the previous claim, we have
$$f(x) | f(y) \implies f^{mn-1}(f(x)) | f^{mn-1}(f(y)) \implies (f^m)^n(x) | (f^n)^m(y) \implies x | y,$$
as claimed.

Define $d(x)$ to be the number of positive divisors of $x$.

Claim 5 For all $x \in \mathbb{N}$, $d(x) = d(f(x))$.
Proof. For any given $x$, let $A$ and $B$ be the sets of positive divisors of $x$ and $f(x)$ respectively. Clearly, by Claim 4 and bijectivity, $f$, when restricted to $A$, is a bijection from $A$ to $B$, whence the claim follows. $\square$

Claim 6 For any given $n$, let its prime factorisation be $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_j^{a_j}$. Then,
$$f(n) = f(p_1)^{a_1} \cdot f(p_2)^{a_2} \cdots f(p_j)^{a_j}$$
where all $f(p_i)$'s are distinct primes.
Proof. We will prove this by strong induction on $\sum a_i$. For $n = 1$, $\sum a_k = 0$. Also, $d(1) = 1 = d(f(1))$. But 1 is the only natural number with only 1 divisor. So $f(1)$ is 1.
Now, if $n$ is a prime, then $d(n) = 2 = d(f(n))$, so $f(n)$ is also prime. Also, it is clear that no two $f(p_i)$'s can be equal as $f$ is bijective.
Now, let's assume that the above statement is true for all $n$ such that $\sum a_i < k$. For $n$ with $\sum a_i = k$, and $k \ge 2$, let $A$ (resp. $B$) be the set of positive divisors of $n$ (resp. $f(n)$). Clearly, by Claim 4, $f$, when restricted to $A$, is a bijection from $A$ to $B$. Since all elements of $A$ are divisors of $n$, all elements of $A$, except $n$ itself, have $\sum a_i < k$, so the stated claim is true for all of them.
Now, if $n$ is a prime power, say $p^k$, then since $A = \{1, p, p^2, \dots, p^k\}$ (as $f(p)$ is prime), $B$ must be $\{1, f(p), f(p)^2, \dots, f(p)^{k-1}, f(n)\}$. But since $B$ is the set of divisors of $f(n)$, the only possible value of $f(n)$ is $f(p)^k$.
Now, if $n$ has multiple prime factors, let's say its prime factorisation is $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_j^{a_j}$. We have
$$p_i^{a_i} \in A, \forall i \le j \implies f(p_i^{a_i}) \in B, \forall i \le j \implies f(p_i)^{a_i} \in B, \forall i \le j$$
by the induction hypothesis. Therefore $\prod f(p_i)^{a_i}$ must also be in $B$, since all $f(p_i)$'s are distinct primes. But we know from our induction hypothesis that this is not the image of any of the proper divisors of $n$ under $f$, and $B$ is the image of $A$ under $f$, hence $\prod f(p_i)^{a_i} = f(n)$ in this case as well. $\square$

Now, consider any prime $p$. We know that $f^{p^{2023}}(f(p)) = f(p)$ and $f^{p^{2023}}(f(p)) = f(p) \implies f^{\gcd(p^{2023}, f(p)^{2023})}(f(p)) = f(p)$. But $p, f(p)$ are primes, thus $\gcd$ is 1 unless $p = f(p)$ but if $f^1(f(p)) = f(p)$, then $f(p) = p$.
Now, by multiplicativity of $f$, we get that $f(x) = x$ for all $x$. $\square$

Solution 2:

Claim 2 For all $x \in \mathbb{N}$, $d(x) \le d(g(x))$.
Proof. $f$ is an injective function from set of divisors of $x$ to set of divisors of $g(x)$. $\square$

If $g(n) = 1$, then $d(g(n)) = 1 \implies d(n) \le 1 \implies d(n) = 1 \implies g(1) = 1$. Further, $f(1) | g(1) = 1 \implies f(1) = 1$.

Claim 3 For any prime $p$, $f(p) = g(p) = p$.
Proof. Let $g(q) = p$. Then $d(q) \le d(p) = 2$ and $q \ne 1$ by injectivity of $g$, so $q$ is also a prime. Further, $f(q) | g(q) = p$ and $f(q) \ne 1$ by injectivity $\implies f(q) = p$. Now,
$$f^{p^{2023}}(q) = f^{p^{2023}-1}(p) = f^{-1}(p) = q = f^{q^{2023}}(q) \implies f^{\gcd(p^{2023}, q^{2023})}(q) = q$$
Now, if $p \ne q$, we get a contradiction. Hence $q = p$, and so $f(q) = g(q) = p$. $\square$

Now we use strong induction on $d(n)$ to prove $f(n) = g(n) = n$. Base cases are $d(n) = 1$ and $d(n) = 2$; these are done since $f(1) = g(1) = 1$ and $f(p) = g(p) = p$ for primes $p$.
Now assume the claim is true for all $m$ such that $d(m) \le k$, for some $k \ge 2$. Let $n$ satisfy $d(n) = k+1$. Suppose $g(y) = n$. By Claim 2, $d(y) \le d(n)$. If $d(y) < d(n)$, by induction hypothesis we have $y = g(y) = n$, contradiction! Hence $d(y) = d(n)$. We have two cases:

Case I: $y$ is not a power of a prime.
Let $y = p_1^{a_1} \cdot p_2^{a_2} \cdots p_j^{a_j}$. Then each $p_i^{a_i}$ has $a_i + 1 < d(y) = k + 1$ divisors, so $f(p_i^{a_i}) = p_i^{a_i}$. Therefore $p_i^{a_i} | g(y) = n$ for all $i \implies y | n$. But, we have $d(y) = d(n)$, so $y = n$, and $g(n) = n$.

Case II: $y = p^a$ for some prime $p$.
Since $d(y) = k+1$, $a = k \ge 2$. Then $d(p^{k-1}) = k \implies f(p^{k-1}) = p^{k-1}$ by induction hypothesis $\implies p^{k-1} | g(y) = n$. If some prime $q \ne p$ divides $n$, then $p^{k-1}q | n \implies d(n) \ge d(p^{k-1}q) = 2k > k + 1$ since $k \ge 2$, contradiction! Therefore $n = p^b$, and $d(n) = k+1 \implies n = p^k = y$. Hence $g(n) = n$ in this case as well.
Then $f(n) | g(n) = n$, so $f(n) \ne n \implies d(f(n)) < d(n) \implies f(n) = f(f(n))$ by induction hypothesis $\implies f(n) = n$ by injectivity, contradiction! Hence $f(n) = g(n) = n$, and we are done by induction.

Solution 3:

Claim 2 $f = g$
Proof. Same as Claim 2 in Solution A1. $\square$

Claim 3 $d(f(x)) = d(x)$.
Proof. $x|y \implies f(x)|f(y)$ and $f$ is bijective. Thus, $d(f(x)) \ge d(x)$.
Now,
$$d(x) \le d(f(x)) \le d(f^2(x)) \le \dots \le d(f^{x^{2023}}(x)) = d(x) \implies d(f(x)) = d(x)$$

Claim 4 For all primes $p$, $f(p) = p$.
Proof. Let $q = f^{-1}(p)$. By Claim 3, $q$ is also a prime. Now,
$$f^{p^{2023}}(q) = f^{p^{2023}-1}(p) = f^{-1}(p) = q = f^{q^{2023}}(q) \implies f^{\gcd(p^{2023}, q^{2023})}(q) = q$$
Now, if $p \ne q$, we get a contradiction. $\square$

Claim 5 $f(p^\alpha) = p^\alpha$ for $\alpha \in \mathbb{N}$.
Proof. Let $t = f^{-1}(p^\alpha)$. Now, if $q$ is a prime such that $q|t$, then $f(q)|p^\alpha \implies q|p \implies p = q$. Thus, $t$ is a power of $p$. Let $t = p^{\alpha'}$ but by Claim 3, $\alpha + 1 = \alpha' + 1 \implies t = p^\alpha$. Thus, $f(p^\alpha) = p^\alpha$. $\square$

Claim 6 $x|f(x)$ for all $x$.
Proof. Let $p^\alpha|x$, for any prime $p$, then $f(p^\alpha)|f(x) \implies p^\alpha|f(x)$. Going over all prime divisors of $x$, we get the desired result. $\square$

$$x | f(x) | f^2(x) | \dots | f^{x^{2023}}(x) | x \implies f(x) = x$$
This uses the fact that $f(x)$ is cyclic for all $x$ but this can easily be avoided as well that for a bijective function $f$, we have $f(x) \ge x$. So consider the smallest $x$ such that $f(x) \neq x$. Now, clearly $x > f^{-1}(x)$ since for all $x$ lesser than it, $f(x) = x$. This is essentially how we proved that $f = g$. Thus, we are done.

Solution 4:

Claim 2 $d(x) \le d(g(x))$
Proof. Same as Claim 2 in Solution A2

Claim 3 $f(p) = p$ for all primes $p$.
Proof. Same as Claim 3 in Solution A2

Claim 4 $f(p^\alpha) = g(p^\alpha) = p^\alpha$ for all primes $p$ and $\alpha \in \mathbb{N}$.
Proof. We proceed by induction. The base case is already done. Now, assume that $\forall k < \alpha$, we have $f(p^k) = g(p^k) = p^k$.
Let $t = g^{-1}(p^\alpha)$. Now, if $q$ is a prime such that $q | t$, then $f(q) | p^\alpha \implies q | p \implies p = q$. Thus, $t$ is a power of $p$. Let $t = p^{\alpha'}$. Now, by Claim 2, $\alpha' \le \alpha$ but $\forall \alpha' < \alpha$, $g(p^{\alpha'}) = p^{\alpha'}$. Thus, $\alpha = \alpha'$. Thus, $g(p^\alpha) = p^\alpha$.
Now, $f(p^\alpha) | p^\alpha$. Thus, $f(p^\alpha) = p^s$ for some $s \le \alpha$ but we know that $f^{-1}(p^s) = p^s$ for all $s < \alpha$. Thus, $s = \alpha$.
Thus, $f(p^\alpha) = g(p^\alpha) = p^\alpha$ as desired.

Claim 5 $x|g(x)$ for all $x \in \mathbb{N}$.
Proof. Let $p^\alpha|x$, then $f(p^\alpha)|g(x) \implies p^\alpha|g(x)$. Going over all prime divisors of $x$, we get that $x|g(x)$ $\square$

Now, we have that $x \le g(x)$ for all $x$. So, consider the smallest $x$ such that $x \neq g(x)$. Then, we get that $g^{-1}(x) > x$ since $\forall y < x, g(y) = y$. This is a contradiction since $g^{-1}(x) > g(g^{-1}(x))$.
Thus, $g(x) = x$ for all $x$. Now, we have that $x|x \implies f(x)|x$ for all $x$ and in particular that $f(x) \le x$ for all $x$. Now, consider the smallest $x$, such that $f(x) \neq x$. Then, $f(x) > x$ since $f^{-1}(y) = y$ for all $y < x$.
Thus, $f(x) = x$ for all $x$ and our conclusion follows.

The general idea for this conclusion and Claim 2 in Solution A1 is that if $a, b$ are bijective on $\mathbb{N}$ and $a(x) \le b(x)$ for all $x$ implies that $a = b$. We earlier use this with $f = a$ and $g = b$. Now, we use $a = id$ and $b = g$. Then finally with $a = f$ and $b = id$.