Difference between revisions of "1986 AIME Problems/Problem 12"

(Solution)
(Solution)
Line 9: Line 9:
 
Thus, <math>S</math> must have exactly 5 elements. <math>S</math> contains both 15 and 14 (otherwise its sum is at most <math>10+11+12+13+15=61</math>). It follows that <math>S</math> cannot contain both <math>a</math> and <math>a-1</math> for any <math>a\leq 13</math>. So now <math>S</math> must contain 13 (otherwise its sum is at most <math>15+14+12+10+8=59</math>), and <math>S</math> cannot contain 12.
 
Thus, <math>S</math> must have exactly 5 elements. <math>S</math> contains both 15 and 14 (otherwise its sum is at most <math>10+11+12+13+15=61</math>). It follows that <math>S</math> cannot contain both <math>a</math> and <math>a-1</math> for any <math>a\leq 13</math>. So now <math>S</math> must contain 13 (otherwise its sum is at most <math>15+14+12+10+8=59</math>), and <math>S</math> cannot contain 12.
  
Now the only way <math>S</math> could have sum at least <math>62=15+14+13+11+9</math> would be if <math>S=\{ 15,14,13,11,9\}</math>. But <math>15+11=13+9</math> so this set does not work, a contradiction. Therefore 61 is indeed the maximum.
+
Now the only way <math>S</math> could have sum at least <math>62=15+14+13+11+9</math> would be if <math>S=\{ 15,14,13,11,9\}</math>. But <math>15+9=13+11</math> so this set does not work, a contradiction. Therefore 61 is indeed the maximum.
  
 
== See also ==
 
== See also ==

Revision as of 23:13, 16 February 2010

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
Invalid username
Login to AoPS