1987 IMO Problems/Problem 4

Problem

Prove that there is no function from the set of non-negative integers into itself such that for every .

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

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

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

---

Solution

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.

Suppose f(m) = n with m = n (mod k). Then by an easy induction on r we find f(m + kr) = n + kr, f(n + kr) = m + k(r+1). We show this leads to a contradiction. Suppose m < n, so n = m + ks for some s > 0. Then f(n) = f(m + ks) = n + ks. But f(n) = m + k, so m = n + k(s - 1) ≥ n. Contradiction. So we must have m ≥ n, so m = n + ks for some s ≥ 0. But now f(m + k) = f(n + k(s+1)) = m + k(s + 2). But f(m + k) = n + k, so n = m + k(s + 1) > n. Contradiction.

So if f(m) = n, then m and n have different residues mod k. Suppose they have r1 and r2 respectively. Then the same induction shows that all sufficiently large s = r1 (mod k) have f(s) = r2 (mod k), and that all sufficiently large s = r2 (mod k) have f(s) = r1 (mod k). Hence if m has a different residue r mod k, then f(m) cannot have residue r1 or r2. For if f(m) had residue r1, then the same argument would show that all sufficiently large numbers with residue r1 had f(m) = r (mod 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.

A better solution by Sawa Pavlov is as follows

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, ... , 1986}. But since f is injective they have the same number of elements, which is impossible since {0, 1, ... , 1986} has an odd number of elements.