IMO 1982 SL 1

Problem

A1 (GBR 3)IMO1 The function f(n) is defined for all positive integers n and takes on nonnegative integer values. Also, for all m, n, f(m + n) −f(m) −f(n) = 0 or 1; f(2) = 0, f(3) > 0, and f(9999) = 3333. Determine f(1982).

Solution

From f(1) + f(1) \leqf(2) = 0 we obtain f(1) = 0. Since 0 < f(3) \leq f(1) + f(2) + 1, it follows that f(3) = 1. Note that if f(3n) \geqn, then f(3n + 3) \geqf(3n) + f(3) \geqn + 1. Hence by induction f(3n) \geqn holds for all n \inN. Moreover, if the inequality is strict for some n, then it is so for all integers greater than n as well. Since f(9999) = 3333, we deduce that f(3n) = n for all n \leq3333. By the given condition, we have 3f(n) \leqf(3n) \leq3f(n) + 2. There- fore f(n) = [f(3n)/3] = [n/3] for n \leq3333. In particular, f(1982) = [1982/3] = 660.