Selection tests for the International Mathematical Olympiad 2013

Since $f$ is strictly increasing, we have $f(n)\ge n$ for all $n$ in $S$.

Assume that there exists an integer $n$ in $S$ such that $f(n)>n$. Let $n_0$ be the smallest such $n$ and write $f(n_0)=n_0+k_0$, for some positive integer $k_0\ge 1$. Again, since $f$ is strictly increasing, we have $f(n)\ge n+k_0$, for all integers $n\ge n_0$.

Because $k_0\ge 1$, we have $$f(n_0+k_0)\ge n_0+2k_0.$$ On the other hand, we have $$f(n_0+k_0)=f(f(n_0))\le 2f(n_0)-n_0=n_0+2k_0$$ We deduce that $$f(n_0+k_0)=n_0+2k_0$$ Because $f(n_0)=n_0+k_0$, $f(n_0+k_0)=(n_0+k_0)+k_0$ and $f$ is strictly increasing, we deduce that $f(n)=n+k_0$, for all $n_0\le n\le n_0+k_0$.

We prove by induction on $m$ that for all integer $n$ such that $$n_0+m{k}_0\le n\le n_0+(m+1)k_0$$ we have $f(n)=n+k_0$. Hence $$f(n)=\{\begin{array}{ll}n+k_0& \text{ if }n\ge n_0\\ n& \text{ otherwise }\end{array}$$ Conversely, if $f$ is such a function and $n\ge n_0$ then $$n+f(f(n))=n+f(n+k_0)=2n+2k_0=2f(n)$$ And if $f(n)=n$, the inequality is clearly satisfied.

Therefore, the solutions to this functional inequality are the functions that can be written as $$f(n)=\{\begin{array}{ll}n+k_0& \text{ if }n\ge n_0\\ n& \text{ otherwise }\end{array}$$ for some $n_0\in S$ and some nonnegative integer $k_0\ge 0$.