1987 IMO Problems/Problem 4

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$ .

We prove that if $f(f(n)) = n + k$ for all $n$ , where $k$ is a fixed positive integer, then $k$ must be even. If $k = 2h$ , then we may take $f(n) = n + h$ .

So if $f(m) = n$ , then $m$ and $n$ have different residues $\pmod k$ . Suppose they have $r_1$ and $r_2$ respectively. Then the same induction shows that all sufficiently large $s \equiv r_1 \pmod k$ have $f(s) \equiv r_2 \pmod k$ , and that all sufficiently large $s \equiv r_2 \pmod k$ have $f(s) \equiv r_1 \pmod k$ . Hence if $m$ has a different residue $r \mod k$ , then $f(m)$ cannot have residue $r_1$ or $r_2$ . For if $f(m)$ had residue $r_1$ , then the same argument would show that all sufficiently large numbers with residue $r_1$ had $f(m) \equiv r \pmod k$ . Thus the residues form pairs, so that if a number is congruent to a particular residue, then $f$ of the number is congruent to the pair of the residue. But this is impossible for $k$ odd.

Solution by Sawa Pavlov:

Let $N$ be the set of non-negative integers. Put $A = N - f(N)$ (the set of all $n$ such that we cannot find $m$ with $f(m) = n$ ). Put $B = f(A)$ .

Note that $f$ is injective because if $f(n) = f(m)$ , then $f(f(n)) = f(f(m))$ so $m = n$ . We claim that $B = f(N) - f(f(N))$ . Obviously $B$ is a subset of $f(N)$ and if $k$ belongs to $B$ , then it does not belong to $f(f(N))$ since $f$ is injective. Similarly, a member of $f(f(N))$ cannot belong to $B$ .

Clearly $A$ and $B$ are disjoint. They have union $N - f(f(N))$ which is $\{0, 1, 2, \ldots , 1986\}$ . But since $f$ is injective they have the same number of elements, which is impossible since $\{0, 1, \ldots , 1986\}$ has an odd number of elements.

1987 IMO (Problems)
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5