Difference between revisions of "1986 AIME Problems/Problem 12"
Mathcool2009 (talk | contribs) (→Solution) |
Mathcool2009 (talk | contribs) (→Solution) |
||
Line 7: | Line 7: | ||
− | 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>, or the subsets <math>\{a,14\}</math> and <math>\{a-1,15\}</math> would have the same sum. 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, or the subsets <math>\{12,15\}</math> and <math>\{13,14\}</math> would have the same sum. |
− | 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 | + | 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 the subsets <math>\{9,15\}</math> and <math>\{11,13\}</math> have the same sum, so this set does not work, a contradiction to the givens. Therefore no <math>S</math> with sum at least 62 is possible and 61 is indeed the maximum. |
== See also == | == See also == |
Revision as of 15:34, 3 January 2014
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 must have more than 4 elements, otherwise its sum would be at most if it had 4 elements.
But also, can't have at least 6 elements. To see why, note that of its subsets have at most four elements (the number of subsets with no elements plus the number of subsets with one element plus the number of subsets with two elements plus the number of subsets with three elements plus the number of subsets with 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 to the givens.
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 , or the subsets and would have the same sum. So now must contain 13 (otherwise its sum is at most ), and cannot contain 12, or the subsets and would have the same sum.
Now the only way could have sum at least would be if . But the subsets and have the same sum, so this set does not work, a contradiction to the givens. Therefore no with sum at least 62 is possible and 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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.