IMO 1998 SL 21

Origin: CAN

Problem

Let a0, a1, a2, . . . be an increasing sequence of nonnegative inte- gers such that every nonnegative integer can be expressed uniquely in the form ai + 2aj + 4ak, where i, j, k are not necessarily distinct. Determine a1998.

Solution

Such a sequence is obviously strictly increasing. We note that it must be unique. Indeed, given a0, a1, . . . , an−1, then an is the least positive integer not of the form ai + 2aj + 4ak, i, j, k < n. We easily get that the first few an’s are 0, 1, 8, 9, 64, 65, 72, 73, . . .. Let {cn} be the increasing sequence of all positive integers that consist of zeros and ones in base 8, i.e., those of the form t0 + 23t1 + \cdot \cdot \cdot + 23qtq where ti \in{0, 1}. We claim that an = cn. To prove this, it is enough to show that each m \inN can be uniquely written as ci + 2cj + 4ck. If m = t0 +2t1+\cdot \cdot \cdot+2rtr (ti \in{0, 1}), then m = ci +2cj +22ck is obviously possible if and only if ci = t0 + 23t3 + 26t6 + \cdot \cdot \cdot , cj = t1 + 23t4 + . . . , and ck = t2 + 23t5 + \cdot \cdot \cdot . Hence for n = s0 + 2s1 + \cdot \cdot \cdot + 2rsr we have an = s0 + 8s1 + \cdot \cdot \cdot + 8rsr. In particular, 1998 = 2 + 22 + 23 + 26 + 27 + 28 + 29 + 210, so a1998 = 8 + 82 + 83 + 86 + 87 + 88 + 89 + 810 = 1227096648. Second solution. Define f(x) = xa0+xa1+\cdot \cdot \cdot . Then the assumed property of {an} gives f(x)f(x2)f(x4) =  i,j,k xai+2aj+4ak =  n xn = 1 −x. We also get as a consequence f(x2)f(x4)f(x8) = 1−x2 , which gives f(x) = (1 + x)f(x8). Continuing this, we obtain f(x) = (1 + x)(1 + x8)(1 + x82) \cdot \cdot \cdot . Hence the an’s are integers that have only 0’s and 1’s in base 8.