IMO 1998 SL 17

Origin: GBR

Problem

A sequence of integers a1, a2, a3, . . . is defined as follows: a1 = 1, and for n \geq1, an+1 is the smallest integer greater than an such that ai + aj ̸= 3ak for any i, j, k in {1, 2, . . ., n + 1}, not necessarily distinct. Determine a1998.

Solution

Initially, we determine that the first few values for an are 1, 3, 4, 7, 10, 12, 13, 16, 19, 21, 22, 25. Since these are exactly the numbers of the forms 3k + 1 and 9k + 3, we conjecture that this is the general pattern. In fact, it is easy to see that the equation x + y = 3z has no solution in the set K = {3k + 1, 9k + 3 | k \inN}. We shall prove that the sequence {an} is actually this set ordered increasingly. Suppose an > 25 is the first member of the sequence not belonging to K. We have several cases: (i) an = 3r + 2, r \inN. By the assumption, one of r + 1, r + 2, r + 3 is of the form 3k + 1 (and smaller than an), and therefore is a member ai of the sequence. Then 3ai equals an + 1, an + 4, or an + 7, which is a contradiction because 1, 4, 7 are in the sequence. (ii) an = 9r, r \inN. Then an + a2 = 3(3r + 1), although 3r + 1 is in the sequence, a contradiction. (iii) an = 9r + 6, r \inN. Then one of the numbers 3r + 3, 3r + 6, 3r + 9 is a member aj of the sequence, and thus 3aj is equal to an + 3, an +12, or an +21, where 3, 12, 21 are members of the sequence, again a contradiction. Once we have revealed the structure of the sequence, it is easy to compute a1998. We have 1998 = 4\cdot499+2, which implies a1998 = 9\cdot499+a2 = 4494.