Soit $f : \mathbb{N} \to \mathbb{N}$ qui vérifie $\forall n\in \mathbb{N}, f(f(n))<f(n+1)$. Alors $f$ est la fonction identité $\forall n\in \mathbb{N},\ f(n)=n$.
Montrons d'abord que $f$ est forcément une fonction strictement croissante.
Posons $m_0=\min\{f(n)\ |\ n\in \mathbb{N}\}$, alors ce min est atteint en un certain $n_0\in \mathbb{N}$ je prétends que forcément $n_0=0$. En effet, si $n_0\geq 1$ alors on aurait $f(f(n_0-1))<f(n_0)=m_0$ ce qui contredirait la minimalité de $m_0$. Ainsi $m_0$ est atteint en l'unique point $n_0=0$.
Posons $m_1 = \min\{f(n)\ |\ n\geq 1\}$, alors ce min est atteint en un certain $n_1\geq 1$. On a de plus $f(f(n_1-1))<f(n_1)=m_1$. En particulier par ce qui précède on a forcément $f(n_1-1)=m_0$ et donc $n_1-1=0$ et donc $n_1=1$. Ainsi $m_1$ est atteint en l'unique point $n=1$ et le reste des valeurs prises par $f$ sont strictement plus grandes que $m_1$.
On procède ainsi de suite en posant $m_2$, $m_3$ puis $m_n$ et en faisant une jolie récurrence.
On trouve que $f$ est strictement croissante comme annoncé.
Ensuite on voit qu'il est impossible d'avoir un $n$ tel que $f(n)=n+1$ sinon $f(f(n))=f(n+1)$ ce qui est en contradiction avec $f(f(n))<f(n+1)$. Pour chaque $n$ il y a donc deux choix, ou bien $f(n)<n+1$, ou bien $f(n)>n+1$. Supposons par l'absurde qu'on ait $k_0$ tel que $f(k_0)>k_0+1$ alors en appliquant la stricte croissance de $f$ on trouve $f(f(k_0))>f(k_0+1)$ ce qui est bien sûr en contradiction avec $f(f(n))<f(n+1)$ pour tout $n$.
Ainsi on a $f : \mathbb{N} \to \mathbb{N}$ une fonction strictement croissante et telle que $f(n)<n+1$ (autrement dit $f(n)\leq n$ puisqu'on travaille avec des entiers), il n'est alors pas trop dur de montrer que forcément $f(n)=n$ pour tout $n$.
Réciproquement la fonction identité est bien sûr solution du problème.
