39th IMO 1998 shortlist Problem N4 The sequence a 1 , a 2 , a 3 , ... is defined as follows. a 1 = 1. a n is the smallest integer greater than a n-1 such that we cannot find 1 ≤ i, j, k ≤ n (not necessarily distinct) such that a i + a j = 3a k . Find a 1998 . Solution
: 4494. We show that a 4n+1 = 9n+1, a 4n+2 = 9n+3, a 4n+3 = 9n+4, a 4n+4 = 9n+7. Note that this sequence includes all positive integers which are 1 mod 3 and some of those which are 0 mod 3. Note first that we cannot find a, b, c in the sequence ... 9n+1, 9n+3, 9n+4, 9n+7, ... such that a + b = 3c. No members of the sequence are 2 mod 3, so we cannot have a or b 1 mod 3 (because 3c is 0 mod 3). But if a and b are both 3 mod 9, then their sum is 6 mod 9, so c must be 2 mod 3, which is impossible. So it remains to show that a n satisfies the smallest criterion. Consider first n = 1. We are given that a 1 = 1. a 2 cannot be 2, or we have 1 + 2 = 3.1. Similarly, a 4 cannot be 5 or we have 4 + 5 = 3.3. It cannot be 6 or we have 3 + 6 = 3.3. So n = 1 is established. Now suppose that n is given. We cannot have a 4n+5 = 9n+8 or (9n+8) + (9n+4) = 3(6n+4). We have 6n+4 = 1 mod 3, so 6n+4 is in the sequence. We cannot have a 4n+5 = 9n+9, because (9n+9) + (9n+3) = 3(6n+4). So a 4n+5 = 9(n+1)+1. We cannot have a 4n+6 = 9(n+1)+2, because (9n+11) + (9n+1) = 3(6n+4). So a 4n+6 = 9(n+1)+3. We cannot have a 4n+8 = 9(n+1)+5, because (9n+14) + 7 = 3(3n+7) and 3n+7 = 1 mod 3. We cannot have a 4n+8 = 9(n+1)+6, because (9n+15) + (9n+15) = 3(6n+10) and 6n+10 = 1 mod 3. So the result holds for n+1 and hence for all n. Thus a 1998 = a 4·499+2 = 9·499+3 = 4494. 39th IMO shortlist 1998 © John Scholes jscholes@kalva.demon.co.uk 30 Aug 2002