14th ASU 1980 Problem 17 S is a set of integers. Its smallest element is 1 and its largest element is 100. Every element of S except 1 is the sum of two distinct members of the set or double a member of the set. What is the smallest possible number of integers in S?
Problem 819
Official solution
9 Solution Let n = M(n) + m(n), where M(n) ≥ m(n). Put M 1 (n) = M(n), M 2 (n) = M(M(n)) etc. Then M(100) ≥ 50, M 2 (100) ≥ 25, M 3 (100) ≥ 13, M 4 (100) ≥ 7, M 5 (100) ≥ 4, M 6 (100) ≥ 2 (and obviously n > M(n) ), so we need at least 8 numbers. There are several ways of using 9 numbers. For example, {1, 2, 4, 8, 16, 32, 36, 64, 100}, where 36 = 4 + 32, 100 = 36 + 64 and the others are double another number. Doubling every time does not work: 1, 2, 4, 8, 16, 32, 64, 128. But if we do not double every time, then we cannot get a number larger than 96 with 8 numbers: the best we can do is 1·2 6 ·(3/2) = 96 (on the occasion when we do not double the best we can do is to the largest plus the next largest, or 3/2 x the largest). Hence we need at least 9 numbers. [To be more formal, write the elements as 1 = a 1 < a 2 < ... < a n , then each a i must be a sum of preceding elements. The largest possible a i is 2a i-1 and the next largest a i-1 + a i-2 and so on.] 14th ASU 1980 © John Scholes [email protected] 4 December 2003 Last corrected/updated 4 Dec 03