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.
  
  
It follows that <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+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 $\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+11=13+9$ 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