1986 AIME Problems/Problem 12

Revision as of 23:13, 16 February 2010 by Aunch (talk | contribs) (Solution)

Problem

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

Solution

The maximum is $61$, attained when $S=\{ 15,14,13,11,8\}$. We must now prove that no such set has sum at least 62. Suppose such a set $S$ existed. Then $S$ can't have 4 or less elements, otherwise its sum would be at most $15+14+13+12=54$.

But also, $S$ can't have at least 6 elements. To see why, note that $2^6-1-1-6=56$ of its subsets have at most four elements, so each of them have sum at most 54. By the Pigeonhole Principle, two of these subsets would have the same sum, a contradiction.


Thus, $S$ must have exactly 5 elements. $S$ contains both 15 and 14 (otherwise its sum is at most $10+11+12+13+15=61$). It follows that $S$ cannot contain both $a$ and $a-1$ for any $a\leq 13$. So now $S$ must contain 13 (otherwise its sum is at most $15+14+12+10+8=59$), and $S$ cannot contain 12.

Now the only way $S$ could have sum at least $62=15+14+13+11+9$ would be if $S=\{ 15,14,13,11,9\}$. But $15+9=13+11$ so this set does not work, a contradiction. Therefore 61 is indeed the maximum.

See also

1986 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 11
Followed by
Problem 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions