IMO 1978 SL 9

Let {f(n)} be a strictly increasing sequence of positive

imoshortlistmathematicsolympiad

IMO 1978 SL 9

Origin: GBR

Problem

Let {f(n)} be a strictly increasing sequence of positive integers: 0 < f(1) < f(2) < f(3) < \cdot \cdot \cdot . Of the positive integers not belonging to the sequence, the nth in order of magnitude is f(f(n)) + 1. Determine f(240).

Solution

Since the nth missing number (gap) is f(f(n))+1 and f(f(n)) is a member of the sequence, there are exactly n−1 gaps less than f(f(n)). This leads to f(f(n)) = f(n) + n −1. (1) Since 1 is not a gap, we have f(1) = 1. The first gap is f(f(1)) + 1 = 2. Two consecutive integers cannot both be gaps (the predecessor of a gap is of the form f(f(m))). Now we deduce f(2) = 3; a repeated application of the formula above gives f(3) = 3 + 1 = 4, f(4) = 4 + 2 = 6, f(6) = 9, f(9) = 14, f(14) = 22, f(22) = 35, f(35) = 56, f(56) = 90, f(90) = 145, f(145) = 234, f(234) = 378. Also, f(f(35))+1 = 91 is a gap, so f(57) = 92. Then by (1), f(92) = 148, f(148) = 239, f(239) = 386. Finally, here f(f(148)) + 1 = 387 is a gap, so f(240) = 388.

Second solution. As above, we arrive at formula (1). Then by simple induction it follows that f(Fn + 1) = Fn+1 + 1, where Fk is the Fibonacci sequence (F1 = F2 = 1). We now prove by induction (on n) that f(Fn + x) = Fn+1 + f(x) for all x with 1 \leqx \leqFn−1. This is trivially true for n = 0, 1. Supposing that it holds for n −1, we shall prove it for n: (i) If x = f(y) for some y, then by the inductive assumption and (1) f(Fn + x) = f(Fn + f(y)) = f(f(Fn−1 + y)) = Fn + f(y) + Fn−1 + y −1 = Fn+1 + f(x). (ii) If x = f(f(y))+1 is a gap, then f(Fn+x−1)+1 = Fn+1+f(x−1)+1 is a gap also: Fn+1 + f(x) + 1 = Fn+1 + f(f(f(y))) + 1 = f(Fn + f(f(y))) + 1 = f(f(Fn−1 + f(y))) + 1. It follows that f(Fn + x) = Fn+1 + f(x −1) + 2 = Fn+1 + f(x). Now, since we know that each positive integer x is expressible as x = Fk1 + Fk2 + \cdot \cdot \cdot + Fkr, where 0 < kr ̸= 2, ki \geqki+1 + 2, we obtain f(x) = Fk1+1 + Fk2+1 + \cdot \cdot \cdot + Fkr+1. Particularly, 240 = 233 + 5 + 2, so f(240) = 377 + 8 + 3 = 388. Remark. It can be shown that f(x) = [\alphax], where \alpha = (1 + \sqrt 5)/2.