IMO Shortlist

Throughout the solution, by $\mathbb{N}$ we denote the set of all positive integers. For any function $h: \mathbb{N} \rightarrow \mathbb{N}$ and for any positive integer $k$, define $h^{k}(x)=\underbrace{h(h(\ldots h(x) \ldots))}_{k}$ (in particular, $h^{0}(x)=x$).

Observe that $f\left(g^{k}(x)\right)=f\left(g^{k-1}(x)\right)+1=\cdots=f(x)+k$ for any positive integer $k$, and similarly $g\left(f^{k}(x)\right)=g(x)+k$. Now let $a$ and $b$ be the minimal values attained by $f$ and $g$, respectively; say $f\left(n_{f}\right)=a, g\left(n_{g}\right)=b$. Then we have $f\left(g^{k}\left(n_{f}\right)\right)=a+k, g\left(f^{k}\left(n_{g}\right)\right)=b+k$, so the function $f$ attains all values from the set $N_{f}=\{a, a+1, \ldots\}$, while $g$ attains all the values from the set $N_{g}=\{b, b+1, \ldots\}$.

Next, note that $f(x)=f(y)$ implies $g(x)=g(f(x))-1=g(f(y))-1=g(y)$; surely, the converse implication also holds. Now, we say that $x$ and $y$ are similar (and write $x \sim y$) if $f(x)=f(y)$ (equivalently, $g(x)=g(y)$). For every $x \in \mathbb{N}$, we define $[x]=\{y \in \mathbb{N}: x \sim y\}$; surely, $y_{1} \sim y_{2}$ for all $y_{1}, y_{2} \in[x]$, so $[x]=[y]$ whenever $y \in[x]$.

Now we investigate the structure of the sets $[x]$.

Claim 1. Suppose that $f(x) \sim f(y)$; then $x \sim y$, that is, $f(x)=f(y)$. Consequently, each class $[x]$ contains at most one element from $N_{f}$, as well as at most one element from $N_{g}$.

Proof. If $f(x) \sim f(y)$, then we have $g(x)=g(f(x))-1=g(f(y))-1=g(y)$, so $x \sim y$. The second statement follows now from the sets of values of $f$ and $g$.

Next, we clarify which classes do not contain large elements.

Claim 2. For any $x \in \mathbb{N}$, we have $[x] \subseteq\{1,2, \ldots, b-1\}$ if and only if $f(x)=a$. Analogously, $[x] \subseteq\{1,2, \ldots, a-1\}$ if and only if $g(x)=b$.

Proof. We will prove that $[x] \subseteq \{1,2, \ldots, b-1\} \Longleftrightarrow f(x)>a$; the proof of the second statement is similar.

Note that $f(x)>a$ implies that there exists some $y$ satisfying $f(y)=f(x)-1$, so $f(g(y))= f(y)+1=f(x)$, and hence $x \sim g(y) \geq b$. Conversely, if $b \leq c \sim x$ then $c=g(y)$ for some $y \in \mathbb{N}$, which in turn follows $f(x)=f(g(y))=f(y)+1 \geq a+1$, and hence $f(x)>a$.

Claim 2 implies that there exists exactly one class contained in $\{1, \ldots, a-1\}$ (that is, the class $[n_{g}]$), as well as exactly one class contained in $\{1, \ldots, b-1\}$ (the class $[n_{f}]$). Assume for a moment that $a \leq b$; then $[n_{g}]$ is contained in $\{1, \ldots, b-1\}$ as well, hence it coincides with $[n_{g}]$. So, we get that
$$\begin{equation*} f(x)=a \Longleftrightarrow g(x)=b \Longleftrightarrow x \sim n_{f} \sim n_{g} . \tag{1} \end{equation*}$$

Claim 3. $a=b$.

Proof. By Claim 2, we have $[a] \neq[n_{f}]$, so $[a]$ should contain some element $a' \geq b$ by Claim 2 again. If $a \neq a'$, then $[a]$ contains two elements $\geq a$ which is impossible by Claim 1. Therefore, $a=a' \geq b$. Similarly, $b \geq a$.

Now we are ready to prove the problem statement. First, we establish the following

Claim 4. For every integer $d \geq 0, f^{d+1}\left(n_{f}\right)=g^{d+1}\left(n_{f}\right)=a+d$.

Proof. Induction on $d$. For $d=0$, the statement follows from (1) and Claim 3. Next, for $d>1$ from the induction hypothesis we have $f^{d+1}\left(n_{f}\right)=f\left(f^{d}\left(n_{f}\right)\right)=f\left(g^{d}\left(n_{f}\right)\right)=f\left(n_{f}\right)+d=a+d$. The equality $g^{d+1}\left(n_{f}\right)=a+d$ is analogous.

Finally, for each $x \in \mathbb{N}$, we have $f(x)=a+d$ for some $d \geq 0$, so $f(x)=f\left(g^{d}\left(n_{f}\right)\right)$ and hence $x \sim g^{d}\left(n_{f}\right)$. It follows that $g(x)=g\left(g^{d}\left(n_{f}\right)\right)=g^{d+1}\left(n_{f}\right)=a+d=f(x)$ by Claim 4.

We start with the same observations, introducing the relation $\sim$ and proving Claim 1 from the previous solution.

Note that $f(a)>a$ since otherwise we have $f(a)=a$ and hence $g(a)=g(f(a))=g(a)+1$, which is false.

Claim 2'. $\quad a=b$.

Proof. We can assume that $a \leq b$. Since $f(a) \geq a+1$, there exists some $x \in \mathbb{N}$ such that $f(a)=f(x)+1$, which is equivalent to $f(a)=f(g(x))$ and $a \sim g(x)$. Since $g(x) \geq b \geq a$, by Claim 1 we have $a=g(x) \geq b$, which together with $a \leq b$ proves the Claim.

Now, almost the same method allows to find the values $f(a)$ and $g(a)$.

Claim $3'$. $f(a)=g(a)=a+1$.

Proof. Assume the contrary; then $f(a) \geq a+2$, hence there exist some $x, y \in \mathbb{N}$ such that $f(x)=f(a)-2$ and $f(y)=g(x)$ (as $g(x) \geq a=b$). Now we get $f(a)=f(x)+2=f\left(g^{2}(x)\right)$, so $a \sim g^{2}(x) \geq a$, and by Claim 1 we get $a=g^{2}(x)=g(f(y))=1+g(y) \geq 1+a$; this is impossible. The equality $g(a)=a+1$ is similar.

Now, we are prepared for the proof of the problem statement. First, we prove it for $n \geq a$.

Claim 4'. For each integer $x \geq a$, we have $f(x)=g(x)=x+1$.

Proof. Induction on $x$. The base case $x=a$ is provided by Claim $3'$, while the induction step follows from $f(x+1)=f(g(x))=f(x)+1=(x+1)+1$ and the similar computation for $g(x+1)$.

Finally, for an arbitrary $n \in \mathbb{N}$ we have $g(n) \geq a$, so by Claim $4'$ we have $f(n)+1= f(g(n))=g(n)+1$, hence $f(n)=g(n)$.