Difference between revisions of "1986 AIME Problems/Problem 12"
m (→See also: cat) |
(→Solution) |
||
| Line 4: | Line 4: | ||
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>. | ||
| − | But also, <math>S</math> can't have at least 6 elements. To see why, note that <math>2^6-1-1-6=56</math> 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, contradiction. | + | But also, <math>S</math> can't have at least 6 elements. To see why, note that <math>2^6-1-1-6=56</math> 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, <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+11=13+9</math> so this set does not work, a contradiction. Therefore 61 is indeed the maximum. | ||
| + | |||
== See also == | == See also == | ||
{{AIME box|year=1986|num-b=11|num-a=13}} | {{AIME box|year=1986|num-b=11|num-a=13}} | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 20:38, 19 December 2009
Problem
Let the sum of a set of numbers be the sum of its elements. Let 
be a set of positive integers, none greater than 15. Suppose no two disjoint subsets of have the same sum. What is the largest sum a set with these properties can have?
Solution
The maximum is 
, attained when 
. We must now prove that no such set has sum at least 62. Suppose such a set 
existed. Then can't have 4 or less elements, otherwise its sum would be at most 
.
But also, can't have at least 6 elements. To see why, note that 
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, must have exactly 5 elements. contains both 15 and 14 (otherwise its sum is at most 
). It follows that cannot contain both 
and 
for any 
. So now must contain 13 (otherwise its sum is at most 
), and cannot contain 12.
Now the only way could have sum at least 
would be if 
. But 
so this set does not work, a contradiction. Therefore 61 is indeed the maximum.
See also
| 1986 AIME (Problems • Answer Key • Resources) | ||
| 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 | ||
