Taiwan IMO Selection Camp

The only pair of functions $(f, g)$ satisfying the statement of the problem is $f(n) = n, g(n) = 1$.
From the condition we know that for all positive integers $n$ we have
$$f(f^{g(n)}(n)) < f(n+1).$$
Let us list all the values that the function $f$ can attain in increasing order as $y_1 < y_2 < \dots$ (this sequence may be finite or infinite in length). We will next use mathematical induction to prove that:
$$(i)_n : f(x) = y_n \text{ if and only if } x = n,$$
$$(ii)_n : y_n = n.$$

$n$ has $f(x) = a = y_a$ if and only if $x = a$. Note that this also means that for any $1 \le a < n$
and positive integer $k, f^k(x) = a$ if and only if $x = a$.
Since for $y_1, y_2, \cdots, y_n$ there is exactly one positive integer corresponding to each of them under $f$, therefore $y_{n+1}$ exists. Take any positive integer $x$ such that $f(x) = y_{n+1}$, then $x$ must be greater than $n$ (according to $(i)_1, \cdots, (i)_n$). Substituting $x-1$ into the above inequality gives
$$f(f^{g(x-1)}(x-1)) < f(x) = y_{n+1},$$
therefore if we denote $f^{g(x-1)}(x-1) = b$, then we have
$$b \in 1, \cdots, n$$
If $b < n$, then we would have $x - 1 = b < n$ (because $f^k(x - 1) = b < n$
if and only if $x - 1 = b$), which contradicts $x > n$. Therefore $b = n$, hence $y_n = n$ (because we already know
$y_{n-1} = n - 1$, so $n$ is the smallest positive integer in the range that is greater than $y_{n-1}$), and this proves $(ii)_n$.
So according to $f^{g(x-1)}(x-1) = n$ and $(i)_n$, we know that $x - 1 = n$, that is, the only possible
value of $x$ is $x = n + 1$, and this also proves $(i)_{n+1}$.
By mathematical induction we can know that $(i)_n$ and $(ii)_n$ hold for all positive integers $n$. Therefore $f(n) = n$. Substituting back into the original condition of the problem, we obtain $g^n(n) + g(n+1) = 2$. Since the range of $g(n)$ is the positive integers, we can immediately deduce that $g(n) = 1$.