IMO Shortlist, 2011

The given relation implies
$$\begin{equation*} f\left(f^{g(n)}(n)\right) < f(n+1) \quad \text{ for all } n, \tag{1} \end{equation*}$$
which will turn out to be sufficient to determine $f$.
Let $y_1 < y_2 < \ldots$ be all the values attained by $f$ (this sequence might be either finite or infinite). We will prove that for every positive $n$ the function $f$ attains at least $n$ values, and we have $(\mathrm{i})_n$: $f(x) = y_n$ if and only if $x = n$, and $(\mathrm{ii})_n$: $y_n = n$. The proof will follow the scheme
$$\begin{equation*} (\mathrm{i})_1, (\mathrm{ii})_1, (\mathrm{i})_2, (\mathrm{ii})_2, \ldots, (\mathrm{i})_n, (\mathrm{ii})_n, \ldots \tag{2} \end{equation*}$$
To start, consider any $x$ such that $f(x) = y_1$. If $x > 1$, then (1) reads $f\left(f^{g(x-1)}(x-1)\right) < y_1$, contradicting the minimality of $y_1$. So we have that $f(x) = y_1$ is equivalent to $x = 1$, establishing $(\mathrm{i})_1$.
Next, assume that for some $n$ statement $(\mathrm{i})_n$ is established, as well as all the previous statements in (2). Note that these statements imply that for all $k \geq 1$ and $a < n$ we have $f^{k}(x) = a$ if and only if $x = a$.
Now, each value $y_i$ with $1 \leq i \leq n$ is attained at the unique integer $i$, so $y_{n+1}$ exists. Choose an arbitrary $x$ such that $f(x) = y_{n+1}$; we necessarily have $x > n$. Substituting $x-1$ into (1) we have $f\left(f^{g(x-1)}(x-1)\right) < y_{n+1}$, which implies
$$\begin{equation*} f^{g(x-1)}(x-1) \in \{1, \ldots, n\} \tag{3} \end{equation*}$$
Set $b = f^{g(x-1)}(x-1)$. If $b < n$ then we would have $x-1 = b$ which contradicts $x > n$. So $b = n$, and hence $y_n = n$, which proves (ii)$_n$. Next, from (i)$_n$ we now get $f(k) = n \Longleftrightarrow k = n$, so removing all the iterations of $f$ in (3) we obtain $x-1 = b = n$, which proves (i)$_{n+1}$.
So, all the statements in (2) are valid and hence $f(n) = n$ for all $n$. The given relation between $f$ and $g$ now reads $n + g^{n}(n) = n + 1 - g(n+1) + 1$ or $g^{n}(n) + g(n+1) = 2$, from which it
immediately follows that we have $g(n) = 1$ for all $n$.