Difference between revisions of "2018 AIME I Problems/Problem 9"

(Added new solution and solution page itself.)
 
m (Solution Exclusion Awareness: See if [ works better than {. I am a LATEX novice.)
Line 11: Line 11:
  
 
Case 1.
 
Case 1.
This is probably the simplest: just make a list of possible combinations for <math>{a, b}</math> and <math>{c, d}</math>. We get <math>{1, 15}...{7, 9}</math> for the first and <math>{4, 20}...{11, 13}</math> for the second. That appears to give us <math>7*8=56</math> solutions, right? NO. Because elements can't repeat, take out the supposed sets <math>{a, b, c, d}</math> of <math>{1, 15, 9, 15}, {2, 14, 10, 14}, {3, 13, 11, 13}, {4, 16, 4, 20}, {5, 11, 5, 19}, {5, 11, 11, 13}, {6, 10, 6, 18}, {6, 10, 10, 14}, {7, 9, 9, 15}, {7, 9, 7, 17}</math>. That's ten cases gone. So <math>46</math> for Case 1.
+
This is probably the simplest: just make a list of possible combinations for <math>{a, b}</math> and <math>{c, d}</math>. We get <math>{1, 15}...{7, 9}</math> for the first and <math>{4, 20}...{11, 13}</math> for the second. That appears to give us <math>7*8=56</math> solutions, right? NO. Because elements can't repeat, take out the supposed sets <math>[a, b, c, d}</math> of <math>{1, 15, 9, 15}, {2, 14, 10, 14}, {3, 13, 11, 13}, {4, 16, 4, 20}, {5, 11, 5, 19}, {5, 11, 11, 13}, {6, 10, 6, 18}, {6, 10, 10, 14}, {7, 9, 9, 15}, {7, 9, 7, 17}</math>. That's ten cases gone. So <math>46</math> for Case 1.
  
 
Case 2.
 
Case 2.

Revision as of 18:19, 7 March 2018

How many distinct subsets of $S={1, 2, ..., 19, 20}$ are there such that there are two distinct elements that sum to $16$ and two distinct elements that sum to $24$? Two examples are ${6, 10, 20, 18}$ and ${3, 5, 13, 19}$.

Feel free to correct this problem if the wording isn't verbatim (I know it isn't).

Solutions

Solution Exclusion Awareness

This problem is tricky because it is the capital of a few "bashy" calculations. Nevertheless, the process is straightforward. Call the set ${a, b, c, d}$.

Note that there are only two cases: 1 where $a + b = 16$ and $c + d = 24$ or 2 where $a + b = 16$ and $a + c = 24$. Also note that there is no overlap between the two situations! This is because if they overlapped, adding the two equations of both cases and canceling out gives you $a=d$, which is absurd.

Case 1. This is probably the simplest: just make a list of possible combinations for ${a, b}$ and ${c, d}$. We get ${1, 15}...{7, 9}$ for the first and ${4, 20}...{11, 13}$ for the second. That appears to give us $7*8=56$ solutions, right? NO. Because elements can't repeat, take out the supposed sets $[a, b, c, d}$ (Error compiling LaTeX. Unknown error_msg) of ${1, 15, 9, 15}, {2, 14, 10, 14}, {3, 13, 11, 13}, {4, 16, 4, 20}, {5, 11, 5, 19}, {5, 11, 11, 13}, {6, 10, 6, 18}, {6, 10, 10, 14}, {7, 9, 9, 15}, {7, 9, 7, 17}$. That's ten cases gone. So $46$ for Case 1.

Case 2. We can look for solutions by listing possible $a$ values and filling in the blanks. Start with $a=4$, as that is the minimum. We find ${4, 12, 20, ?}$, and likewise up to $a=15$. But we can't have $a=8$ or $a=12$ because $a=b$ or $a=c$, respectively! Now, it would seem like there are $10$ values for $a$ and $17$ unique values for each $?$, giving a total of $170$, but that is once again not true because there are some repeated values! We can subtract 1 from all pairs of sets that have two elements in common, because those can give us identical sets. There are 3 pairs about $a=8$ and 3 pairs about $a=12$, meaning we lose $6$. That's $164$ for Case 2.

Total gives $\boxed{210}$. Lesson for this problem: Never be scared to attempt an AIME problem. You will oftentimes get it in ~10 minutes.