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

(Solution)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Let the sum of a set of numbers be the sum of its elements. Let <math>\displaystyle S</math> be a set of positive integers, none greater than 15. Suppose no two disjoint subsets of <math>\displaystyle S</math> have the same sum. What is the largest sum a set <math>\displaystyle S</math> with these properties can have?  
+
Let the sum of a set of numbers be the sum of its elements. Let <math>S</math> be a set of positive integers, none greater than 15. Suppose no two disjoint subsets of <math>S</math> have the same sum. What is the largest sum a set <math>S</math> with these properties can have?  
 
== Solution ==
 
== Solution ==
 
The maximum is <math>61</math>, attained when <math>S=\{ 15,14,13,11,8\}</math>. We must now prove that no such set has sum at least 62. Suppose such a set <math>S</math> existed. Then <math>S</math> can't have 4 or less elements, otherwise its sum would be at most <math>15+14+13+12=54</math>.
 
The maximum is <math>61</math>, attained when <math>S=\{ 15,14,13,11,8\}</math>. We must now prove that no such set has sum at least 62. Suppose such a set <math>S</math> existed. Then <math>S</math> can't have 4 or less elements, otherwise its sum would be at most <math>15+14+13+12=54</math>.
Line 15: Line 15:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Revision as of 19:05, 4 July 2013

Problem

Let the sum of a set of numbers be the sum of its elements. Let $S$ be a set of positive integers, none greater than 15. Suppose no two disjoint subsets of $S$ have the same sum. What is the largest sum a set $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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS