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
: 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 1  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 = 1 and hence s 1 = 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 10 -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 11 ≥ 1500 implies s 10 ≥ 750. But s 8 ≤ 255, so a 9 + a 10 ≥ 495, so a 10 ≥ 248. 21st USAMO 1992 © John Scholes jscholes@kalva.demon.co.uk 11 May 2002