39th IMO 1998 shortlist Problem N8 The sequence 0 ≤ a 0 < a 1 < a 2 < ... is such that every non-negative integer can be uniquely expressed as a i + 2a j + 4a k (where i, j, k are not necessarily distinct). Find a 1998 . Solution
: So a 1998 = 8 10 + 8 9 + 8 8 + 8 7 + 8 6 + 8 3 + 8 2 + 8 = 1227096648. After a little experimentation we find that the first few terms are 0, 1, 8, 9, 64, 65. This suggests that each term is a sum of distinct powers of 8. If N is any positive integer, then N is a sum of distinct powers of 2: x = b 0 + b 1 2 + b 2 2 2 + b 3 2 2 + ... , where b i = 0 or 1. Grouping every third term, we get: N = (b 0 + b 3 8 + b 6 8 2 + ... ) + 2(b 1 + b 4 8 + b 7 8 2 + ... ) + 4(b 2 + b 5 8 + b 8 8 2 + ... ) = a + 2b + 4c (*), where a, b, c are each sums of distinct powers of 8. But (*) is evidently unique, because we may write a, b, c as indicated as a sum of powers of 8 and then get the binary expression for N. That is unique, so (*) is unique. Could there be a different sequence A n with the same property? We obviously require A 0 = 0, A 1 = 1. Suppose A n is not the same as a n . Then take m to be the first n at which they disagree. Suppose a m < A m . Then a m must have an expression A i + 2A j + 4A k with i, j and k all < m. But that means that a m has two different expressions using the sequence a n . Contradiction. How do we order the sums of distinct powers of 8? Suppose C = c 0 + c 1 8 + c 2 8 2 + ... + c n 8 n , and D = d 0 + d 1 8 + ... + d n 8 n , where all c i and d i are 0 or 1. Then evidently C < D iff the binary number c 0 c 1 ... c n < d 0 ... d n . So to find the (n+1)th member of the sequence a n we write n in binary and then read it back in base 8. We have 1998 = 1024 + 512 + 256 + 128 + 64 + 8 + 4 + 2. So a 1998 = 8 10 + 8 9 + 8 8 + 8 7 + 8 6 + 8 3 + 8 2 + 8 = 1227096648. 39th IMO shortlist 1998 © John Scholes jscholes@kalva.demon.co.uk 30 Aug 2002