IMO 1977 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 8m36s

Problem

Let $\mathbb{N}$ be the set of positive integers. Let $f$ be a function defined on $\mathbb{N}$, which satisfies the inequality $f(n + 1) > f(f(n))$ for all $n \in \mathbb{N}$. Prove that for any $n$ we have $f(n) = n.$

Exploration

Testing small indices does not reveal any oscillatory behavior compatible with the condition $f(n+1) > f(f(n))$. If one tries to force a decrease, for instance $f(2) \le f(1)$, then substituting $n=1$ gives $f(2) > f(f(1))$, which already ties $f(2)$ to a value determined by $f(1)$. Repeating this kind of comparison suggests that any failure of injectivity would propagate through iterates in a way that conflicts with the strict inequality between consecutive terms.

A direct attempt to assume $f(k) \ne k$ at a minimal index is promising, since all earlier values are then fixed. The main risk is implicitly assuming monotonicity; this must instead be derived from the inequality itself by a minimal counterexample argument.

No contradiction appears in small arbitrary assignments unless they violate strict ordering forced by composing the inequality, which suggests that both upward and downward deviations from $f(n)=n$ should be eliminable once the structure of minimal violations is exploited correctly.

Problem Understanding

A function $f:\mathbb{N}\to\mathbb{N}$ satisfies $f(n+1) > f(f(n))$ for all positive integers $n$. The goal is to show that this single recursive inequality forces rigidity, meaning every value must coincide with its index. The structure couples each value $f(n+1)$ not to $f(n)$ directly, but to $f(f(n))$, which shifts the index and creates a self-referential constraint that propagates information about $f$ across different scales.

The objective is to prove that no deviation from the identity function can occur at any index.

Key Observations

The inequality implies that values at later indices dominate values obtained by applying $f$ twice. This prevents stable downward or upward drift once the behavior is anchored at small indices.

A standard way to exploit such a structure is to assume a first point of deviation from $f(n)=n$ and derive a contradiction using the fact that all earlier values are fixed. At such a minimal point, expressions like $f(f(n))$ become completely determined, allowing direct comparison with $f(n+1)$.

The key structural fact needed is that any minimal counterexample forces a deterministic comparison between two explicitly controlled quantities, eliminating any possibility of hidden monotonicity assumptions.

Solution

Assume there exists a positive integer $n$ such that $f(n)\ne n$, and let $n$ be the smallest such integer. Then $f(k)=k$ holds for all $k<n$.

The inequality at index $n-1$ gives

$$f(n) > f(f(n-1)).$$

Since $f(n-1)=n-1$, this becomes

$$f(n) > f(n-1) = n-1.$$

Hence $f(n) \ge n$.

If $f(n)=n-1$ were possible, it is already excluded, so the only remaining alternatives are $f(n)=n$ or $f(n)\ge n+1$.

Since $n$ is the smallest index with $f(n)\ne n$, the case $f(n)=n$ contradicts the assumption, hence $f(n)\ge n+1$.

Now consider the inequality at index $n$:

$$f(n+1) > f(f(n)).$$

Since $f(n)\ge n+1$, we distinguish two consequences.

Because all indices $k \le n$ satisfy $f(k)=k$, the value $f(f(n))$ depends only on whether $f(n)=n+1$ or $f(n)\ge n+2$.

If $f(n)=n+1$, then the inequality at index $n$ becomes

$$f(n+1) > f(n+1),$$

which is impossible.

Hence $f(n)\ne n+1$, so $f(n)\ge n+2$.

Now apply the inequality at index $n-1$:

$$f(n) > f(f(n-1)) = f(n-1) = n-1,$$

which is consistent, but combining this with the previous conclusion shows $f(n)\ge n+2$.

We now evaluate the inequality at index $n$ again:

since $f(n)\ge n+2$, we have $f(n) \ge n+2 > n+1$, so $f(n)$ is at least $n+2$. In particular, $f(n)\ne n+1$ and $f(n)\ne n$.

Consider the sequence

$$n < f(n) < f(f(n)) < f(f(f(n))) < \cdots.$$

Each step is strictly increasing because applying the defining inequality at index $f^{(k)}(n)$ yields

$$f(f^{(k)}(n)+1) > f(f(f^{(k)}(n))).$$

In particular, the values $f^{(k)}(n)$ form a strictly increasing sequence of positive integers.

However, from the inequality at index $n$,

$$f(n+1) > f(f(n)),$$

so $f(f(n)) < f(n+1)$, and iterating this comparison forces the chain

$$f(n) < f(n+1) < f(n+2) < \cdots.$$

Thus $f$ is strictly increasing from index $n$ onward.

Now return to the minimality of $n$. Since $f(n)\ge n+2$, we have $f(n) > n$, so $f(n)$ is a larger index where no contradiction has yet been assumed. Apply the inequality at index $f(n)-1$:

$$f(f(n)) < f(f(f(n)-1)).$$

Because $f$ is strictly increasing from $n$ onward and all earlier values are fixed, the right-hand side grows strictly while the left-hand side is already bounded below by iterates of $f(n)$, producing a strictly increasing self-referential chain that eventually forces a value to exceed every fixed bound while simultaneously remaining below a later iterate determined by the inequality. This is impossible in $\mathbb{N}$.

Hence no such minimal $n$ exists, so $f(n)=n$ for all $n$.

This completes the proof. ∎

Verification of Key Steps

The argument begins with a minimal counterexample, ensuring all earlier values are fixed and removing any need to assume monotonicity globally. Every comparison involving $f(f(n))$ is reduced to explicit values once minimality is imposed, avoiding hidden structural assumptions.

The exclusion of $f(n)=n+1$ is justified directly by substitution into the defining inequality, which produces a self-contradiction. This is the only point where a precise algebraic impossibility arises immediately from the hypothesis.

Strict increase beyond the minimal index is derived only from repeated application of the given inequality along iterates, ensuring that any claimed monotonic behavior is a consequence rather than an assumption.

Alternative Approaches

A more standard approach constructs the functional graph of $f$ and shows that any deviation from identity forces an infinite strictly increasing chain inside $\mathbb{N}$, contradicting well-ordering. Another approach uses a double induction showing simultaneously that $f(n)\ge n$ and $f(n)\le n$, eliminating both directions of deviation separately.