IMO 1995 SL 27

Problem

S5 (FIN) For positive integers n, the numbers f(n) are defined induc- tively as follows: f(1) = 1, and for every positive integer n, f(n+1) is the greatest integer m such that there is an arithmetic progression of positive integers a1 < a2 < \cdot \cdot \cdot < am = n for which f(a1) = f(a2) = \cdot \cdot \cdot = f(am). Prove that there are positive integers a and b such that f(an + b) = n + 2 for every positive integer n.

Solution

Computing the first few values of f(n), we observe the following pattern: f(4k) = k, k \geq3, f(8) = 3; f(4k + 1) = 1, k \geq4, f(5) = f(13) = 2; f(4k + 2) = k −3, k \geq7, f(2) = 1, f(6) = f(10) = 2, f(14) = f(18) = 3, f(26) = 4; f(4k + 3) = 2. We shall prove these statements simultaneously by induction on n, having verified them for k \leq7. (i) Let n = 4k. Since f(3) = f(7) = \cdot \cdot \cdot = f(4k −1) = 2, we have f(4k) \geqk. But f(n) \leqmaxm<n f(m) + 1 \leq(k −1) + 1, so f(4k) = k. (ii) Let n = 4k + 1, k \geq7. Since f(4k) = k and f(m) < k for m < 4k, we deduce that f(4k + 1) = 1. (iii) Let n = 4k + 2, k \geq7. Since f(17) = f(21) = \cdot \cdot \cdot = f(4k + 1) = 1, we obtain f(4k +2) \geqk −3. On the other hand, if f(4k +1) = f(4k +1− d) = 1, then d \geq8, and 4k + 1 −8(k −3) < 0. So f(4k + 2) = k −3. (iv) Let n = 4k+3, k \geq7. We have f(4k+2) = k−3 and f(m) = k−3 for exactly one m < 4k+2 (namely for m = 4k−12); hence f(4k+3) = 2. Therefore, for example, f(4n + 8) = n + 2 for all n; hence we can take a = 4 and b = 8.