1986 AIME Problem 12

Attempt Problem 12 of the 1986 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1986 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Let the sum of a set of numbers be the sum of its elements. Let SS be a set of positive integers, none greater than 15.15. Suppose no two disjoint subsets of SS have the same sum. What is the largest sum a set SS with these properties can have?

Answer: 61
Concepts:extremal argumentmeansubsets
Difficulty rating: 3270
Small Hint:

If SS had six elements, compare the variance of its 6464 subset sums with that of 6464 consecutive integers

Big Hint:

After bounding the size of S,S, inspect the five-element subsets whose sums exceed the candidate

Solution:

First, SS has at most five elements. If it had six elements s1,,s6,s_1,\ldots,s_6, then its 6464 subset sums would all be distinct: equality between two subset sums, after cancelling their common elements, would violate the given condition.

Choose a subset uniformly at random and let XX be its sum. Then Var(X)=14i=16si214(102+112++152)=9554. \begin{gathered} \operatorname{Var}(X) =\frac14\sum_{i=1}^6s_i^2\\ {}\leq\frac14(10^2+11^2+\cdots+15^2)\\ {}=\frac{955}{4}. \end{gathered} On the other hand, XX is uniform on 6464 distinct integers. The least possible variance for 6464 distinct integers occurs when they are consecutive, and is 642112=13654, \frac{64^2-1}{12}=\frac{1365}{4}, a contradiction.

A set with at most four elements has sum at most 12+13+14+15=54.12+13+14+15=54. There are only seven five-element subsets of {1,,15}\{1,\ldots,15\} whose sums are at least 62.62. Each fails, as witnessed by the following equal sums:

{8,12,13,14,15}:\{8,12,13,14,15\}: 13+14=12+15.13+14=12+15. {9,11,13,14,15}:\{9,11,13,14,15\}: 11+13=9+15.11+13=9+15. {9,12,13,14,15}:\{9,12,13,14,15\}: 13+14=12+15.13+14=12+15.

{10,11,12,14,15}:\{10,11,12,14,15\}: 11+14=10+15.11+14=10+15. {10,11,13,14,15}:\{10,11,13,14,15\}: 11+13=10+14.11+13=10+14.

{10,12,13,14,15}:\{10,12,13,14,15\}: 12+13=10+15.12+13=10+15. {11,12,13,14,15}:\{11,12,13,14,15\}: 12+13=11+14.12+13=11+14.

Thus the answer is at most 61.61.

The set {8,11,13,14,15}\{8,11,13,14,15\} attains 61.61. Its 3232 subset sums, in order, are 0,8,11,13,14,15,19,21,22,23,24,25,26,27,28,29,32,33,34,35,36,37,38,39,40,42,46,47,48,50,53,61, \begin{gathered} 0,8,11,13,14,15,19,21,\\ 22,23,24,25,26,27,28,29,\\ 32,33,34,35,36,37,38,39,\\ 40,42,46,47,48,50,53,61, \end{gathered} all distinct. Equal sums from arbitrary subsets would, after deleting their intersection, give equal sums from disjoint subsets, so this verifies the required property.

← Problem 11#11
Full Exam

Problem 12 in Other Years