51st IMO Shortlisted Problems

Throughout the solution, by $\mathbb{N}$ we denote the set of all positive integers. For any function $h:\mathbb{N}\to \mathbb{N}$ and for any positive integer $k$, define $h^k(x)=\underset{k}{\underbrace{h(h(\dots h(x)\dots ))}}$ (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,\dots \}$, while $g$ attains all the values from the set $N_g=\{b,b+1,\dots \}$.

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,\dots ,b-1\}$ if and only if $f(x)=a$. Analogously, $[x]\subseteq \{1,2,\dots ,a-1\}$ if and only if $g(x)=b$.

Proof. We will prove that $[x]\subseteq \{1,2,\dots ,b-1\}⟺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)\ge b$. Conversely, if $b\le 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\ge a+1$, and hence $f(x)>a$.

Claim 2 implies that there exists exactly one class contained in $\{1,\dots ,a-1\}$ (that is, the class $[n_g]$), as well as exactly one class contained in $\{1,\dots ,b-1\}$ (the class $[n_f]$). Assume for a moment that $a\le b$; then $[n_g]$ is contained in $\{1,\dots ,b-1\}$ as well, hence it coincides with $[n_g]$. So, we get that $$\begin{array}{c}f(x)=a⟺g(x)=b⟺x\sim n_f\sim n_g.\end{array}\text{\hspace{1em}(1)}$$

Claim 3. $a=b$.

Proof. By Claim 2, we have $[a]\ne [n_f]$, so $[a]$ should contain some element $a^{\prime }\ge b$ by Claim 2 again. If $a\ne a^{\prime }$, then $[a]$ contains two elements $\ge a$ which is impossible by Claim 1. Therefore, $a=a^{\prime }\ge b$. Similarly, $b\ge a$.

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

Claim 4. For every integer $d\ge 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\ge 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.

---

Alternative solution.

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'. $a=b$.

Proof. We can assume that $a\le b$. Since $f(a)\ge 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)\ge b\ge a$, by Claim 1 we have $a=g(x)\ge b$, which together with $a\le b$ proves the Claim.

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

Claim $3^{\prime }$. $f(a)=g(a)=a+1$.

Proof. Assume the contrary; then $f(a)\ge 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)\ge a=b$). Now we get $f(a)=f(x)+2=f\left(g^2(x)\right)$, so $a\sim g^2(x)\ge a$, and by Claim 1 we get $a=g^2(x)=g(f(y))=1+g(y)\ge 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\ge a$.

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

Proof. Induction on $x$. The base case $x=a$ is provided by Claim $3^{\prime }$, 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)\ge a$, so by Claim $4^{\prime }$ we have $f(n)+1=f(g(n))=g(n)+1$, hence $f(n)=g(n)$.