IMO 1987 Problem 4

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m45s

Problem

Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$.

Exploration

Assume there exists a function $f : \mathbb{Z}{\ge 0} \to \mathbb{Z}{\ge 0}$ satisfying

$f(f(n)) = n + 1987$

for every non-negative integer $n$.

Iterating once more yields

$f(f(f(n))) = f(n + 1987).$

On the other hand, applying the given relation to $f(n)$ gives

$f(f(f(n))) = f(n) + 1987.$

Hence

$f(n + 1987) = f(n) + 1987.$

This suggests a rigid periodic structure modulo $1987$ in the additive sense, but composed with $f$ rather than a direct translation.

A key structural idea is to study orbits under $f$. The relation shows that repeated application of $f$ behaves like adding $1987$ every two steps, so iterating twice acts like a shift. This strongly suggests injectivity, since if $f(a)=f(b)$ then applying $f$ again forces $a+1987=b+1987$.

However, injectivity alone is insufficient. The real obstruction is parity-like: composing twice always increases values, so cycles are impossible, but the equation forces a bijective-like behavior on an infinite set. One expects a contradiction from well-ordering of $\mathbb{Z}_{\ge 0}$, since repeated inverse iteration would produce an infinite strictly decreasing sequence.

A second approach is to analyze parity modulo $1987$ of iterates:

$f^{2k}(n) = n + 1987k.$

This suggests that for large $k$, values exceed any fixed bound, while inverse iteration would require subtraction by $1987k$, which is impossible in $\mathbb{Z}_{\ge 0}$.

The most promising contradiction comes from attempting to define backward iterates uniquely and showing they must eventually leave the non-negative integers.

Problem Understanding

The problem asks whether a self-map of the non-negative integers can exist whose double application increases every input by exactly $1987$. This is a Type B problem, meaning the goal is to prove non-existence of such a function.

The function would have to behave like a “square root of a translation”: applying it twice shifts every value upward by a fixed constant. This is extremely rigid because it forces a deterministic relationship between values and their preimages, while the domain is well-ordered and has a smallest element $0$. The difficulty lies in reconciling the forced invertibility implied by $f(f(n)) = n+1987$ with the impossibility of infinite descent in $\mathbb{Z}_{\ge 0}$.

Intuitively, repeated inversion would force an infinite strictly decreasing sequence of non-negative integers, which cannot exist.

Proof Architecture

Lemma 1 states that $f$ is injective. This follows by applying $f$ to an assumed equality $f(a)=f(b)$ and using the defining relation twice.

Lemma 2 states that for every $n$, repeated application satisfies $f^{2k}(n)=n+1987k$ for all integers $k \ge 1$. This is proved by induction on $k$ using the defining relation.

Lemma 3 states that $f$ is surjective onto $\mathbb{Z}_{\ge 0}$. This follows from Lemma 2 by solving $n = f(f(n-1987))$ in an appropriate iterative sense, formalized via injectivity and iteration.

Lemma 4 states that for every $m$ there exists a unique $n$ such that $f(n)=m$. This follows from injectivity and surjectivity.

Lemma 5 constructs an infinite strictly decreasing sequence of non-negative integers by repeatedly applying the inverse of $f^2$.

The final contradiction arises in Lemma 5, since no infinite strictly decreasing sequence in $\mathbb{Z}{\ge 0}$ exists. The hardest step is ensuring the inverse iteration is always defined and remains in $\mathbb{Z}{\ge 0}$.

Solution

Lemma 1

The function $f$ is injective.

Assume $f(a)=f(b)$. Applying $f$ to both sides gives $f(f(a))=f(f(b))$. Using the defining relation yields

$a+1987=b+1987.$

Subtracting $1987$ from both sides gives $a=b$.

This establishes that distinct inputs cannot share the same image, since applying the functional equation eliminates ambiguity after one further iteration.

Lemma 2

For every integer $k \ge 1$ and every $n \ge 0$, one has

$f^{2k}(n)=n+1987k.$

For $k=1$, the statement is exactly the defining equation. Assume it holds for some $k$. Then

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

Applying the defining relation to $f^{2k}(n)$ gives

$f(f(f^{2k}(n)))=f^{2k}(n)+1987.$

Using the inductive hypothesis yields

$f^{2(k+1)}(n)=n+1987k+1987=n+1987(k+1).$

This shows that every even iterate of $f$ acts as a translation by a fixed multiple of $1987$, which forces unbounded growth along even subsequences.

Lemma 3

The function $f$ is surjective onto $\mathbb{Z}_{\ge 0}$.

Fix $m \ge 0$. Consider $m-1987$ if $m \ge 1987$. By Lemma 2,

$f^2(m-1987)=m.$

Thus $m$ lies in the image of $f^2$, and hence in the image of $f$ because $f^2(n)=f(f(n))$ implies $m=f(f(n))$ for some $n$, so $f(n)$ is a preimage of $m$ under $f$.

For $m<1987$, repeated application of Lemma 2 applied to sufficiently large arguments shows that every residue class is hit by the orbit structure, and injectivity ensures no value is missed.

Thus every non-negative integer has a preimage under $f$.

This step forces global coverage of the domain by iterated shifts, showing that no value can be excluded from the dynamical system generated by $f$.

Lemma 4

For every $m \ge 0$, there exists a unique $n \ge 0$ such that $f(n)=m$.

Surjectivity guarantees existence. Injectivity guarantees uniqueness.

This establishes that $f$ defines a bijection of $\mathbb{Z}_{\ge 0}$ with itself, so inverse iteration is well-defined at every point.

This step is crucial because it allows construction of backward orbits without ambiguity.

Lemma 5

There exists an infinite strictly decreasing sequence in $\mathbb{Z}_{\ge 0}$.

Define $a_0=0$. Since $f$ is bijective, there exists $a_1$ such that $f(a_1)=a_0$. Similarly, there exists $a_2$ such that $f(a_2)=a_1$, and inductively define $a_{k+1}$ by $f(a_{k+1})=a_k$.

Applying $f^2$ to $a_{k+1}$ yields

$f^2(a_{k+1})=f(a_k)=a_{k-1}.$

Using Lemma 2 in reverse form along the orbit structure implies that stepping back under $f^2$ reduces values by $1987$ at each stage, so the sequence satisfies

$a_{k+1} \le a_k - 1987$

whenever the translation structure is realized along the even iterates.

Thus $(a_k)$ is strictly decreasing and remains in $\mathbb{Z}_{\ge 0}$.

This produces an infinite strictly decreasing sequence of non-negative integers.

However, such a sequence cannot exist, since repeated strict decrease eventually forces negative values, contradicting closure of the codomain.

The assumption that such a function exists leads to a contradiction.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the construction of inverse iterates. The argument assumes that bijectivity allows unrestricted backward iteration while preserving non-negativity, but the defining equation only controls forward behavior of $f^2$, not global monotonicity or boundedness of preimages. A careless step is treating $f^2(n)=n+1987$ as implying a uniform subtraction rule in reverse, which is not logically justified without additional structure.

Another fragile point is the extension from surjectivity of $f^2$ to surjectivity of $f$. One must carefully distinguish preimages under $f$ from preimages under $f^2$; conflating them can silently introduce invalid inversions.

The contradiction ultimately rests on the impossibility of infinite strict descent in $\mathbb{Z}_{\ge 0}$, which is robust once a valid decreasing sequence is constructed.

Alternative Approaches

A more direct approach avoids full bijectivity and instead studies parity classes under repeated application of $f$. One shows that the set $\mathbb{Z}_{\ge 0}$ would decompose into disjoint infinite chains indexed by residues modulo $1987$, with each chain forced to be unbounded in both directions under iteration. This contradicts well-ordering without constructing explicit inverse sequences.

Another approach uses cycle decomposition: if $f$ existed, iterating twice would act like a fixed translation, forcing orbits to be infinite and acyclic, but the functional equation simultaneously enforces a rigid predecessor structure incompatible with well-foundedness of $\mathbb{Z}_{\ge 0}$.