\section*{Problem 17}

\(\mathrm{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 \(\mathrm{S}\) ?

\section*{Answer}


\section*{Solution}

Let \(n=M(n)+m(n)\), where \(M(n) \geq m(n)\). Put \(M^{1}(n)=M(n), M^{2}(n)=M(M(n))\) etc. Then \(\mathrm{M}(100) \geq 50, \mathrm{M}^{2}(100) \geq 25, \mathrm{M}^{3}(100) \geq 13, \mathrm{M}^{4}(100) \geq 7, \mathrm{M}^{5}(100) \geq 4, \mathrm{M}^{6}(100) \geq 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} \cdot(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 \mathrm{x}\) the largest). Hence we need at least 9 numbers. [To be more formal, write the elements as \(1=a_{1}<a_{2}<\ldots<a_{n}\), then each \(a_{i}\) must be a sum of preceding elements. The largest possible \(a_{i}\) is \(2 a_{i-1}\) and the next largest \(a_{i-1}+a_{i-2}\) and so on.]

