IMO 1993 SL 8

Origin: IND

Problem

Define a sequence ⟨f(n)⟩\infty n=1 of positive integers by f(1) = 1 and f(n) = . f(n −1) −n, if f(n −1) > n; f(n −1) + n, if f(n −1) \leqn, for n \geq2. Let S = {n \inN | f(n) = 1993}. (a) Prove that S is an infinite set. (b) Find the least positive integer in S. (c) If all the elements of S are written in ascending order as n1 < n2 < n3 < \cdot \cdot \cdot , show that lim i\to\infty ni+1 ni = 3.

Solution

Suppose that f(n) = 1 for some n > 0. Then f(n + 1) = n + 2, f(n + 2) = 2n + 4, f(n + 3) = n + 1, f(n + 4) = 2n + 5, f(n + 5) = n, and so by induction f(n + 2k) = 2n + 3 + k, f(n + 2k −1) = n + 3 −k for k = 1, 2, . . . , n + 2. Particularly, n′ = 3n + 3 is the smallest value greater than n for which f(n′) = 1. It follows that all numbers n with f(n) = 1 are given by n = bi, where b0 = 1, bn = 3bn−1 + 3. Furthermore, bn = 3 + 3bn−1 = 3 + 32 + 32bn−2 = \cdot \cdot \cdot = 3 + 32 + \cdot \cdot \cdot + 3n + 3n = = 1 2(5 \cdot 3n −3). It is seen from above that if n \leqbi, then f(n) \leqf(bi −1) = bi + 1. Hence if f(n) = 1993, then n \geqbi \geq1992 for some i. The smallest such bi is

b7 = 5466, and f(bi + 2k −1) = bi + 3 −k = 1993 implies k = 3476. Thus the least integer in S is n1 = 5466 + 2 \cdot 3476 −1 = 12417. All the elements of S are given by ni = bi+6 +2k −1, where bi+6 +3−k = 1993, i.e., k = bi+6−1990. Therefore ni = 3bi+6−3981 = 1 2(5\cdot3i+7−7971). Clearly S is infinite and limi\to\infty ni+1 ni = 3.