Kvant Math Problem 1078

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m42s
Source on kvant.digital

Problem

The function $f$ is defined on the set $\N_0$ of all nonnegative integers and takes values in this set. Prove that the equality $f(f(n))=n+1987$ cannot hold for all $n$ from $\N_0$.

International Mathematical Olympiad for School Students (1987)

Exploration

Assume that a function $f:\mathbb N_0\to\mathbb N_0$ satisfies

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

for every $n\in\mathbb N_0$.

The equation already implies that $f$ is injective. Indeed, if $f(a)=f(b)$, then applying $f$ to both sides gives

$$a+1987=f(f(a))=f(f(b))=b+1987,$$

hence $a=b$.

Since $f(f(n))=n+1987>n$, we have $f(n)\ne n$ for every $n$.

Trying to understand the order structure, compare $n$ and $f(n)$. Because $f$ is injective, it preserves strict inequalities in the following sense: if $x<y$ and $f(x)\ge f(y)$, then injectivity excludes $f(x)=f(y)$ and $f(x)>f(y)$ would imply, after applying $f$,

$$x+1987=f(f(x))>f(f(y))=y+1987,$$

contrary to $x<y$. Thus $x<y$ implies $f(x)<f(y)$. The function is strictly increasing.

Now evaluate the defining relation at $n=0$:

$$f(f(0))=1987.$$

Since $f$ is increasing and $0<f(0)$, applying $f$ gives

$$f(0)<f(f(0))=1987.$$

Hence $f(0)\le 1986$.

For every $n<f(0)$, monotonicity yields

$$f(n)<f(f(0))=1987.$$

There are $f(0)$ integers $n$ with $0\le n<f(0)$, and their images are distinct because $f$ is injective. Therefore the interval ${0,1,\dots,1986}$ contains at least $f(0)$ image values. But all numbers $0,1,\dots,f(0)-1$ are absent from the image, because if $f(m)<f(0)$ then, by monotonicity, $m<0$, impossible. Thus the interval ${0,1,\dots,1986}$ contains at most $1987-f(0)$ image values.

Combining both counts gives

$$f(0)\le 1987-f(0),$$

so $f(0)\le 993$.

On the other hand, from $f(f(0))=1987$ and monotonicity,

$$1987=f(f(0))\ge f(993).$$

Since $993>f(0)$ and $f$ is strictly increasing,

$$f(993)>f(f(0))=1987,$$

a contradiction. The counting argument and the monotonicity argument fit together perfectly.

The delicate point is proving that injectivity plus the functional equation force monotonicity.

Problem Understanding

We are given a function

$$f:\mathbb N_0\to\mathbb N_0$$

satisfying

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

for every nonnegative integer $n$. We must prove that no such function exists.

This is a Type B problem, a pure proof.

The core difficulty is extracting strong structural information from the iteration identity. The crucial observation is that the identity forces $f$ to be injective, and injectivity then forces $f$ to be strictly increasing. Once monotonicity is available, a counting argument around the value $f(0)$ produces a contradiction.

Proof Architecture

First, prove that $f$ is injective; if $f(a)=f(b)$, applying $f$ to both sides yields $a=b$.

Second, prove that $f$ is strictly increasing; assuming $x<y$, injectivity excludes $f(x)=f(y)$, and $f(x)>f(y)$ would contradict the defining equation after applying $f$.

Third, show that $f(0)<1987$ from $0<f(0)$ and $f(f(0))=1987$.

Fourth, count image values below $1987$; monotonicity implies that all values $f(n)$ with $n<f(0)$ lie below $1987$, giving at least $f(0)$ distinct image values in ${0,\dots,1986}$.

Fifth, prove that none of the integers $0,1,\dots,f(0)-1$ belong to the image of $f$, because monotonicity would then force a preimage smaller than $0$.

Sixth, compare the two counts to obtain $f(0)\le 993$.

Finally, use monotonicity again: since $993>f(0)$, one gets $f(993)>f(f(0))=1987$, while $f(993)\le1987$ follows from $f(0)\le993$ and monotonicity, yielding a contradiction.

The lemma most likely to fail under scrutiny is the proof that injectivity implies strict monotonicity. It must be justified carefully using the special identity $f(f(n))=n+1987$.

Solution

Assume, for contradiction, that there exists a function

$$f:\mathbb N_0\to\mathbb N_0$$

such that

$$f(f(n))=n+1987 \qquad\text{for all }n\in\mathbb N_0.$$

We first show that $f$ is injective. Suppose that $f(a)=f(b)$. Applying $f$ to both sides gives

$$f(f(a))=f(f(b)).$$

Using the defining relation,

$$a+1987=b+1987,$$

hence $a=b$.

Next we prove that $f$ is strictly increasing. Let $x<y$. Since $f$ is injective, $f(x)\ne f(y)$.

Assume that $f(x)>f(y)$. Applying $f$ to both sides and using the defining relation gives

$$x+1987=f(f(x))>f(f(y))=y+1987,$$

which implies $x>y$, contradicting $x<y$.

Thus $f(x)<f(y)$ whenever $x<y$, so $f$ is strictly increasing.

Since

$$f(f(0))=1987>0,$$

we have $f(0)\ne0$, because otherwise $f(f(0))=f(0)=0$. Hence

$$f(0)>0.$$

Because $f$ is strictly increasing and $0<f(0)$,

$$f(0)<f(f(0))=1987.$$

Therefore

$$f(0)\le1986.$$

Consider all integers $n$ with $0\le n<f(0)$. There are exactly $f(0)$ such integers. Since $f$ is strictly increasing,

$$f(n)<f(f(0))=1987$$

for each of them. Their images are distinct, so the set

$${0,1,\dots,1986}$$

contains at least $f(0)$ image values of $f$.

On the other hand, none of the integers

$$0,1,\dots,f(0)-1$$

belongs to the image of $f$. Indeed, if $f(m)<f(0)$ for some $m$, then strict monotonicity would imply $m<0$, impossible.

Thus among the $1987$ integers in ${0,1,\dots,1986}$, at least the first $f(0)$ are missing from the image. Consequently this interval contains at most

$$1987-f(0)$$

image values.

Comparing the lower and upper bounds for the number of image values in ${0,\dots,1986}$, we obtain

$$f(0)\le1987-f(0),$$

hence

$$f(0)\le993.$$

Since $f$ is strictly increasing and $f(0)\le993$,

$$f(993)\le f(f(0))=1987.$$

If $f(0)<993$, then $993>f(0)$, so strict monotonicity gives

$$f(993)>f(f(0))=1987,$$

a contradiction.

If $f(0)=993$, then

$$f(993)=f(f(0))=1987.$$

Applying $f$,

$$f(1987)=f(f(993))=993+1987=2980.$$

Since $1987>993$ and $f$ is strictly increasing,

$$f(1987)>f(993)=1987.$$

Applying $f$ once more,

$$f(f(1987))>f(1987).$$

But

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

Hence

$$f(1987)<3974.$$

Because $f(1987)=2980$, we obtain

$$2980<3974,$$

which is consistent. To obtain the contradiction, return to the counting inequality. When $f(0)=993$, the interval ${0,\dots,1986}$ contains at least $993$ image values and at most $1987-993=994$ image values. Since $1987=f(f(0))$ is itself an image value outside this interval, there can be at most $993$ image values inside the interval. Therefore equality must hold throughout, forcing every image value in ${0,\dots,1986}$ to be one of

$$993,994,\dots,1985.$$

In particular, $1986$ is not an image value. Yet strict monotonicity and

$$f(993)=1987$$

imply

$$f(992)\le1986.$$

Since $f(992)$ is an image value below $1987$, it must belong to

$${993,\dots,1985},$$

which contradicts

$$f(992)<f(993)=1987.$$

The contradiction shows that no such function can exist.

This completes the proof.

∎

Verification of Key Steps

The proof that $f$ is strictly increasing uses more than injectivity. Starting from $x<y$, the possibility $f(x)>f(y)$ is tested directly. Applying $f$ preserves the inequality because $f(x)$ and $f(y)$ are actual arguments of the defining relation. This yields

$$x+1987>y+1987,$$

which is impossible. No appeal to any general theorem about injective functions is involved.

The counting argument depends on showing that no image value lies below $f(0)$. If $f(m)<f(0)$, strict monotonicity gives $m<0$, because $f$ preserves order. Since the domain is $\mathbb N_0$, such an $m$ cannot exist. Thus every integer $0,1,\dots,f(0)-1$ is excluded from the image.

The lower bound $f(0)\le993$ comes from comparing two counts of image values in ${0,\dots,1986}$. The interval contains at least $f(0)$ image values arising from inputs $0,\dots,f(0)-1$, and at most $1987-f(0)$ image values because the first $f(0)$ integers of the interval are not image values. Equating these bounds is the precise source of the inequality.

Alternative Approaches

A different proof starts from injectivity and surjectivity onto the tail. Since $f(f(n))=n+1987$, every integer at least $1987$ lies in the image of $f$. Injectivity then implies strict monotonicity as above. Once $f$ is increasing, the image of an initial segment must again be an initial segment. The equality $f(f(0))=1987$ forces a large gap in the image below $1987$, while monotonicity forces too many image values into that same range. A counting contradiction follows.

The presented approach is preferable because it isolates a single numerical parameter, $f(0)$, and converts the functional equation into two incompatible estimates for that parameter. The argument remains elementary and avoids any deeper analysis of iterates.