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

m (Solution)
 
(10 intermediate revisions by 7 users not shown)
Line 2: Line 2:
 
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?  
 
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>.
+
By using the greedy algorithm, we obtain <math>\boxed{061}</math>, with <math>S=\{ 15,14,13,11,8\}</math>. We must now prove that no such set has sum greater than 61. Suppose such a set <math>S</math> existed. Then <math>S</math> must have more than 4 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, a contradiction.
+
<math>S</math> can't have more than 5 elements. To see why, note that at least <math>\dbinom{6}{0} + \dbinom{6}{1} + \dbinom{6}{2} + \dbinom{6}{3} + \dbinom{6}{4}=57</math> of its subsets have at most four elements (the number of subsets with no elements plus the number of subsets with one element and so on), and each of them have sum at most 54. By the Pigeonhole Principle, two of these subsets would have the same sum. If those subsets were disjoint, we would directly arrive at a contradiction; if not, we could remove the common elements to get two disjoint subsets.
  
 +
Thus, <math>S</math> would have to have 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.
  
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 the subsets <math>\{9,15\}</math> and <math>\{11,13\}</math> have the same sum, so this set does not work. Therefore no <math>S</math> with sum greater than 61 is possible and 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 ==

Latest revision as of 19:41, 1 September 2020

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

By using the greedy algorithm, we obtain $\boxed{061}$, with $S=\{ 15,14,13,11,8\}$. We must now prove that no such set has sum greater than 61. Suppose such a set $S$ existed. Then $S$ must have more than 4 elements, otherwise its sum would be at most $15+14+13+12=54$.

$S$ can't have more than 5 elements. To see why, note that at least $\dbinom{6}{0} + \dbinom{6}{1} + \dbinom{6}{2} + \dbinom{6}{3} + \dbinom{6}{4}=57$ of its subsets have at most four elements (the number of subsets with no elements plus the number of subsets with one element and so on), and each of them have sum at most 54. By the Pigeonhole Principle, two of these subsets would have the same sum. If those subsets were disjoint, we would directly arrive at a contradiction; if not, we could remove the common elements to get two disjoint subsets.

Thus, $S$ would have to have 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$, or the subsets $\{a,14\}$ and $\{a-1,15\}$ would have the same sum. So now $S$ must contain 13 (otherwise its sum is at most $15+14+12+10+8=59$), and $S$ cannot contain 12, or the subsets $\{12,15\}$ and $\{13,14\}$ would have the same sum.

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 the subsets $\{9,15\}$ and $\{11,13\}$ have the same sum, so this set does not work. Therefore no $S$ with sum greater than 61 is possible and 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