USAMO 92/3 solution

21st USAMO 1992

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, ... , 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, ... , 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₁ < a₂ < ... < a₁₁. Put s_n = a₁ + ... + a_n. Take N such that s_N-1 < 1500 ≤ s_N. Note that 1500 must be a sum of some of the integers so certainly 1500 ≤ s₁₁. Equally we obviously have a₁ = 1, a₂ = 2, so N is well-defined and we have 1 < N ≤ 11. Now if 1 < k ≤ N, we have s_k-1 < 1500 and hence s_k-1 + 1 ≤ 1500. So some sum of distinct a_i must equal s_k-1 + 1 and it must involve an a_i with i > k-1 since s_k-1 < s_k-1 + 1. Hence a_k ≤ s_k-1 + 1 for 1 < k ≤ N.

Now an easy induction gives s_k ≤ 2_k - 1. We must have a₁ = 1 and hence s₁ = 1, so it is true for k = 1. Suppose it is true for k-1. Then a_k ≤ s_k-1 + 1 ≤ 2^k-1, so s_k = s_k-1 + a_k ≤ 2^k-1 - 1 + 2^k-1 = 2^k - 1, so it is true for k. Hence for all k ≤ N. But 2¹⁰ -1 = 1023 < 1500, so if N < 11, then s_N < 1500. Contradiction. Hence N = 11.

We have s_k = s_k-1 + a_k ≤ 2s_k-1 + 1. Hence s_k-1 ≥ (s_k - 1)/2. So s₁₁ ≥ 1500 implies s₁₀ ≥ 750. But s₈ ≤ 255, so a₉ + a₁₀ ≥ 495, so a₁₀ ≥ 248.

21st USAMO 1992