## Problem 3

A set of 11 distinct positive integers has the property that we can find a subset with sum $n$ for any $n$ between 1 and 1500 inclusive. What is the smallest possible value for the second largest element?


## Solution

Answer: 248.

By taking the integers to be $1,2,4,8, \ldots, 1024$ we can generate all integers up to 2047 . But by taking some integers smaller, we can do better. For example, 1, 2, 4, .., 128, 247, 248, 750 gives all integers up to 1500 . We can obviously use the integers $1,2,4, \ldots, 128$ to generate all integers up to 255 . Adding 248 gives all integers from 256 up to 503 . Then adding 247 gives all integers from 504 to 750 . So adding 750 gives all integers up to 1500 . We show that we cannot do better than this.

Let the integers be $a_{1}\mathrm{k}-1$ since $\mathrm{s}_{\mathrm{k}-1}<\mathrm{s}_{\mathrm{k}-1}+1$. Hence $\mathrm{a}_{\mathrm{k}} \leq \mathrm{s}_{\mathrm{k}-1}+1$ for $1<\mathrm{k} \leq \mathrm{N}$.

Now an easy induction gives $\mathrm{s}_{\mathrm{k}} \leq 2_{\mathrm{k}}-1$. We must have $\mathrm{a}_{1}=1$ and hence $\mathrm{s}_{1}=1$, so it is true for $\mathrm{k}=1$.

Suppose it is true for $\mathrm{k}-1$. Then $\mathrm{a}_{\mathrm{k}} \leq \mathrm{s}_{\mathrm{k}-1}+1 \leq 2^{\mathrm{k}-1}$, so $\mathrm{s}_{\mathrm{k}}=\mathrm{s}_{\mathrm{k}-1}+\mathrm{a}_{\mathrm{k}} \leq 2^{\mathrm{k}-1}-1+2^{\mathrm{k}-1}=2^{\mathrm{k}}-1$, so it is true for $\mathrm{k}$. Hence for all $\mathrm{k} \leq \mathrm{N}$. But $2^{10}-1=1023<1500$, so if $\mathrm{N}<11$, then $\mathrm{s}_{\mathrm{N}}<1500$. Contradiction. Hence $\mathrm{N}=11$.

We have $\mathrm{s}_{\mathrm{k}}=\mathrm{s}_{\mathrm{k}-1}+\mathrm{a}_{\mathrm{k}} \leq 2 \mathrm{~s}_{\mathrm{k}-1}+1$. Hence $\mathrm{s}_{\mathrm{k}-1} \geq\left(\mathrm{s}_{\mathrm{k}}-1\right) / 2$. So $\mathrm{s}_{11} \geq 1500$ implies $\mathrm{s}_{10} \geq 750$. But $\mathrm{s}_{8} \leq 255$, so $\mathrm{a}_{9}+$ $\mathrm{a}_{10} \geq 495$, so $\mathrm{a}_{10} \geq 248$.

