Team Selection Test for EGMO 2024

Answer: $f(x)\equiv 1$ and $f(x)=x$. By putting $a=1$ to $f(\phi (a))=\phi (f(a))$ we get $f(1)=\phi (f(1))$ and hence $f(1)=1$. By putting $a=2$ we get $f(1)=\phi (f(2))$ and since $f(1)=1$ we get that either $f(2)$ is either 1 or 2.

Case 1: $f(2)=1$. Since $1=f(2)=f(\phi (3))=\phi (f(3))$ we get that $f(3)$ is either 1 or 2. But since $(3-1)\mid f(3)-f(1)$ we get that $f(3)=1$. By induction we show that $f(n)=1$ for all positive integers $n$. Assume that $f(a)=1$ for all $a=1,2,\dots ,n-1$. Then since $f(\phi (n))=\phi (f(n))$ and $\phi (n)\le n-1$ we get $\phi (f(n))=1$ and hence $f(n)$ is either 1 or 2. Finally again since $n-(n-2)\mid f(n)-f(n-2)$ we get that $f(n)=1$. Done.

Case 2: $f(2)=2$. By induction we show that $f(n)=n$ for all positive integers $a$. Assume that $f(a)=a$ for all $a=1,2,\dots ,n-1$. By the first condition and by inductive hypothesis for each $1\le a\le n-1$ we have $n-a\mid f(n)-a$ or equivalently $n-a\mid f(n)-n$. Therefore, for each integer $1\le m\le n-1$ we have $m\mid f(n)-n$. Hence the common divisor $M$ of all integers $1\le m\le n-1$ also divides $f(n)-n$; $f(n)=Ms+n$, where $s$ is integer. Then since $\phi (n)<n$ by the second condition and by inductive hypothesis $\phi (n)=\phi (Ms+n)$. On the other hand, since each integer $k$ with $(n,k)=1$ and $k<n$ divides $M$ we have $(k,Ms+n)=1$. Therefore, $\phi (n)\le \phi (Ms+n)$. If $s\ne 0$ then $(Ms+n-1,Ms+n)=1$ and hence we get that $\phi (n)<\phi (Ms+n)$. This contradiction shows that $s=0$ and $f(n)=n$. Done.