IMO 1993 SL 6

Origin: GER

Problem

Let N = {1, 2, 3, . . .}. Determine whether there exists a strictly increasing function f : N \toN with the following properties: f(1) = 2; (1) f(f(n)) = f(n) + n (n \inN). (2)

Solution

Notice that for \alpha = 1+ \sqrt , \alpha2n = \alphan+n for all n \inN. We shall show that f(n) = / \alphan + 1 (the closest integer to \alphan) satisfies the requirements. Observe that f is strictly increasing and f(1) = 2. By the definition of f, |f(n) −\alphan| \leq1 2 and f(f(n)) −f(n) −n is an integer. On the other hand, |f(f(n)) −f(n) −n| = |f(f(n)) −f(n) −\alpha2n + \alphan| = |f(f(n)) −\alphaf(n) + \alphaf(n) −\alpha2n −f(n) + \alphan| = |(\alpha −1)(f(n) −\alphan) + (f(f(n)) −\alphaf(n))| \leq(\alpha −1)|f(n) −\alphan| + |f(f(n)) −\alphaf(n)| \leq1 2(\alpha −1) + 1 2 = 1 2\alpha < 1, which implies that f(f(n)) −f(n) −n = 0.