IMO 1987 SL 22

Origin: VIE

Problem

Does there exist a function f : N \toN, such that f(f(n)) = n + 1987 for every natural number n?

Solution

Suppose that there exists such function f. Then we obtain f(n + 1987) = f(f(f(n))) = f(n) + 1987 for all n \inN, and from here, by induction, f(n + 1987t) = f(n) + 1987t for all n, t \inN. Further, for any r \in{0, 1, . . ., 1986}, let f(r) = 1987k + l, k, l \inN, l \leq1986. We have r + 1987 = f(f(r)) = f(l + 1987k) = f(l) + 1987k, and consequently there are two possibilities: (i) k = 1 ⇒f(r) = l + 1987 and f(l) = r; (ii) k = 0 ⇒f(r) = l and f(l) = r + 1987;

in both cases, r ̸= l. In this way, the set {0, 1, . . ., 1986} decomposes to pairs {a, b} such that f(a) = b and f(b) = a + 1987, or f(b) = a and f(a) = b + 1987. But the set {0, 1, . . ., 1986} has an odd number of elements, and cannot be decomposed into pairs. Contradiction.