Iranian Mathematical Olympiad

a) Let $$f(x)=\{\begin{array}{ll}2& x=1\\ 3& x=2\\ 1& x=3\\ x& x\notin \{1,2,3\}\end{array}g(x)=\{\begin{array}{ll}3& x=1\\ 1& x=2\\ 2& x=3\\ x& x\notin \{1,2,3\}\end{array}$$ It is easy to check that $g^2=f$ and $f^2=g$.

b) Suppose $g$ is a function that $f\to g$ and $g\to f$. It means that there are integers $m$ and $n$ such that $f^m=g$ and $g^n=f$. So $f^{mn}=f$ and $f$ generates at most $mn-1$ functions. Therefore, there are only a finite number of functions $g$.

c) Define $g:\mathbb{R}\to \mathbb{R}$ as follows: $$g(x)=\{\begin{array}{ll}x+1& x\in \mathbb{Z}\\ x& x\notin \mathbb{Z}\end{array}$$ Let $f$ be a real function such that $f\to g$ ($f^k=g$). Note that $g$ is bijective, and hence $f$ is bijective too. If $f(z_0)\notin \mathbb{Z}$ for some $z_0\in \mathbb{Z}$, we have: $$f(z_0)=g(f(z_0))=f^{k+1}(z_0)=f(g(z_0))=f(z_0+1),$$ which leads to a contradiction since $f$ is injective. Hence $f(\mathbb{Z})\subseteq \mathbb{Z}$. Now, for each integer number $z$ we have: $$f(z+1)=f(g(z))=f^{k+1}(z)=g(f(z))=f(z)+1.$$ Therefore, $f(z)=z+t$ for some integer number $t$ and every integer number $z$. Next, for every integer number $z$ we have: $$z+kt=f^k(z)=g(z)=z+1\Rightarrow kt=1\Rightarrow k=t=1.$$ Therefore, $f$ must be equal to $g$.

d) If $f^m(x)=x^3$ and $f^n(x)=x^5$ for some $m,n\in \mathbb{N}$, then $x^{3n}=f^{mn}(x)=x^{5m}$. Therefore, $3^n=5^m$. But this equation does not have any solutions in natural numbers.

e) First, we prove a lemma. Lemma 1. Let $f:\mathbb{R}\to \mathbb{R}$ be a function and $a>b$ two integer numbers such that $f^a$ and $f^b$ are both polynomials of degree 1. Then $f^{a-b}$ is also a polynomial of degree 1. Proof. $f^{a-b}(x)=f^a\circ ((f^b{)}^{-1}(x))$, and the inverse of every polynomial with degree 1 is again a polynomial of degree 1. $\square$

Now, assume that $f^m=P$, $f^n=Q$ and $(m,n)=d$ for some $m,n,d\in \mathbb{N}$. Referring to the lemma and using Euclidean algorithm, $f^d$ is a polynomial of degree 1 that generates both $P$ and $Q$.