IMO 1993/B2 solution

IMO 1993

Problem B2

Does there exist a function f from the positive integers to the positive integers such that f(1) = 2, f(f(n)) = f(n) + n for all n, and f(n) < f(n+1) for all n?

Answer

Yes: f(n) = [g*n + ½], where g = (1 + √5)/2 = 1.618 ... .

Solution

This simple and elegant solution is due to Suengchur Pyun

Let g(n) = [g*n + ½]. Obviously g(1) = 2. Also g(n+1) = g(n) + 1 or g(n) + 2, so certainly g(n+1) > g(n).

Consider d(n) = g* [g*n + ½] + ½ - ( [g*n + ½] + n). We show that it is between 0 and 1. It follows immediately that g(g(n)) = g(n) + n, as required.

Certainly, [g*n + ½] > g*n - ½, so d(n) > 1 - g/2 > 0 (the n term has coefficient g² - g - 1 which is zero). Similarly, [g*n + ½] ≤ g*n + ½, so d(n) ≤ g/2 < 1, which completes the proof.

I originally put up the much clumsier result following:

Take n = b_rb_r-1 ... b₀ in the Fibonacci base. Then f(n) = b_rb_r-1 ... b₀0. This satisfies the required conditions.

Let u₀ = 1, u₁ = 2, ... , u_n=u_n-1+u_n-2, ... be the Fibonacci numbers. We say n = b_rb_r-1 ... b₀ in the Fibonacci base if b_r = 1, every other b_i = 0 or 1, no two adjacent b_i are non-zero, and n = b_ru_r + ... + b₀u₀. For example, 28 = 1001010 because 28 = 21 + 5 + 2.

We have to show that every n has a unique expression of this type. We show first by induction that it has at least one expression of this type. Clearly that is true for n = 1. Take u_r to be the largest Fibonacci number ≤ n. Then by induction we have an expression for n - u_r. The leading term cannot be u_i for i > r - 2, for then we would have n >= u_r + u_r-1 = u_r+1. So adding u_r to the expression for n - u_r gives us an expression of the required type for n, which completes the induction.

We show that u_r + u_r-2 + u_r-4 + ... = u_r+1 - 1. Again we use induction. It is true for r = 1 and 2. Suppose it is true for r - 1, then u_r+1 + u_r-1 + ... = u_r+2 - u_r + u_r-1 + u_r-3 + ... = u_r+2 - u_r + u_r - 1 = u_r+2 - 1. So it is true for r + 1. Hence it is true for all r. Now we can prove that the expression for n is unique. It is for n = 1. So assume it is for all numbers < n, but that the expression for n is not unique, so that we have n = u_r + more terms = u_s + more terms. If r = s, then the expression for n - u_r is not unique. Contradiction. So suppose r > s. But now the second expression is at most u_s+1 - 1 which is less than u_r. So the expression for n must be unique and the induction is complete.

It remains to show that f satisfies the required conditions. Evidently if n = 1 = u₀, then f(n) = u₁ = 2, as required. If n = u_a₁ + ... + u_{a_r}, then f(n) = u_a₁+1 + ... + u_{a_r+1} and f(f(n)) = u_a₁+2 + ... + u_{a_r+2}. So f(n) + n = (u_a₁ + u_a₁+1) + ... + (u_{a_r} + u_{a_r+1}) = f(f(n)).

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

39th IMO 1998