IMO 1977 · Problem 6

Let \(f(n)\) be a function defined on the set of all positive integers and having all its values in the same set. Prove that if \[ f(n+1)>f(f(n)) \] for each positive integer \(n\), then \[ f(n)=n\quad\text{for each }n. \]

Official text of the problem. Official problem paper (PDF)

Solution

We first prove by induction on \(k\) that \[ f(m)\ge k\qquad\text{for every integer }m\ge k. \] For \(k=1\), this follows because all values of \(f\) are positive integers.

Suppose the claim holds for some \(k\ge1\), and let \(m\ge k+1\). Since \(m-1\ge k\), the induction hypothesis gives \(f(m-1)\ge k\). Applying the same hypothesis to the argument \(f(m-1)\), we obtain \[ f(f(m-1))\ge k. \] Consequently, \[ f(m)>f(f(m-1))\ge k. \] As \(f(m)\) is an integer, \(f(m)\ge k+1\), completing the induction. Taking \(k=m\), we conclude that \[ f(m)\ge m\qquad\text{for every positive integer }m. \]

In particular, applying this bound at \(m=f(n)\) gives \[ f(n+1)>f(f(n))\ge f(n). \] Thus \(f\) is strictly increasing.

Now fix any positive integer \(n\). If \(f(n)\ge n+1\), monotonicity would imply \[ f(f(n))\ge f(n+1), \] contrary to the given inequality. Hence \(f(n)<n+1\), so \(f(n)\le n\). Together with \(f(n)\ge n\), this proves \[ \boxed{f(n)=n\quad\text{for every positive integer }n.} \]

The solution was checked against John Scholes' IMO solution archive (Kalva).