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

Revision as of 21:48, 3 July 2019

Problem

Find the number of four-element subsets of $\{1,2,3,4,\dots, 20\}$ with the property that two distinct elements of a subset have a sum of $16$ , and two distinct elements of a subset have a sum of $24$ . For example, $\{3,5,13,19\}$ and $\{6,10,20,18\}$ are two such subsets.

Solutions

Solution 1

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 cannot be true.

Case 1. This is probably the simplest: just make a list of possible combinations for $\{a, b\}$ and $\{c, d\}$ . We get $\{1, 15\}\dots\{7, 9\}$ for the first and $\{4, 20\}\dots\{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 $\{1, 15, 9, 15\}, \{2, 14, 10, 14\}, \{3, 13, 11, 13\}, \{4, 12, 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. Write out all the sets and we get $6$ . That's $164$ for Case 2.

Total gives $\boxed{210}$ .

-expiLnCalc

Solution 2

This is gonna be real quick. I considered making this an extension to solution one, but I've decided to make it a separate solution. (Disclaimer: I'm not formatting this properly so if anyone wants to format it correctly using Latex, feel free.)

Let's say our four elements in our subset are $a,b,c,d$ . We have two cases.

First, we can have where two distinct elements sum to $16$ and two other distinct elements sum to $24$ . Basically, one way of representing this is having $a+b = 16$ and $c+d = 24$ . The order of the elements / the element letters themselves don't matter since they are all on equal grounds at the start. List out possibilities for $a+b$ $(\text{i.e. } 1+15, 2+14, 3+13 \text{ etc.})$ but don't include $8+8$ because those are the same elements and that is restricted. Then list out the possibilities for $c+d \text{ }(\text{i.e. } 4+20, 5+19, 6+18, \text{ etc.})$ but again don't list $12+12$ because they are the same elements. This will give you $7 \cdot 8$ elements, which is $56$ . However, as stated above, we have overlap. Just count starting from $a+b - 15,14,13,4,5,11,6,10,7,9$ all overlap once, which is $10$ , thus $56 - 10 = 46$ cases in this first case. Note that $12$ wasn't included because again, if $c+d = 24$ , $c$ and $d$ cannot be $12$ .

Our second case is when $a+b = 16$ and $b+c = 24$ . Here, one element $(b)$ is included twice in both equations. We can easily see that $a, b, c$ will never equal each other. Furthermore, there are 17 choices for $d (20 - 3$ included elements $)$ for each $b$ . Listing out the possible $b$ s, we go from $15,14,13,11,10,9,7,6,5,4$ . Do not include $8$ or $12$ because if they are included, then $a/c$ will be the same as $b$ , which is restricted. There are $10$ options there, and since $10 \cdot 17 = 170$ , you would think there are $170$ cases and we are done. That's the tricky part about this problem - not the computation itself, but how easily sillies can be made. This is because, if $a+b = 16$ and $b+c = 24$ , notice that $c-a = 8$ . That means that if $b-d$ is also $8$ , then we have a double-counted set. Starting with $b=15$ , we have $15, 14, 13, 11, 10, 9$ (where $d$ is $7, 6, 5, 3, 2, 1)$ . That means there are $6$ double-counted cases.

Adding these up, we get $46+170-6 = \boxed{210}.$

~IronicNinja ~ $\LaTeX$ by AlcBoy1729 ~Formatted by ojaswupadhyay $\[\]$ Again if anyone wants to format this better feel free, I was just lazy.

Solution 0

This code works:

 int num = 0;
 for(int i = 1; i <= 20; i++){
   for(int j = i+1; j <= 20; j++){
     for(int k = j+1; k <= 20; k++){
       for(int m = k+1; m <= 20; m++){
         if(i+j==16 || i + k == 16 || i + m == 16 || j + k == 16
         || j + m == 16 || k + m == 16){
           if(i+j==24 || i+k==24 || i+m==24 || j+k==24 || j+m == 24 || k+m==24){
             num++; 
           }
         }
       }
     }
   }
 }
 cout << num << endl;

@@ Line 23: / Line 23: @@
 This is gonna be real quick. I considered making this an extension to solution one, but I've decided to make it a separate solution. (Disclaimer: I'm not formatting this properly so if anyone wants to format it correctly using Latex, feel free.)
-Let's say our four elements in our subset are <math>a,b,c,d</math>. We have two cases. First, we can have where two distinct elements sum to <math>16</math> and two other distinct elements sum to <math>24</math>. Basically, one way of representing this is having <math>a+b = 16</math> and <math>c+d = 24</math>. The order of the elements/the element letters themselves don't matter since they are all on equal grounds at the start. List out possibilities for <math>a+b (\text{i.e.}, 1+15, 2+14, 3+13 \text{etc.})</math> but don't include <math>8+8</math> because those are the same elements and that is restricted. Then list out the possibilities for <math>c+d (\text{i.e.} 4+20, 5+19, 6+18, \text{etc.})</math> but again don't list <math>12+12</math> because they are the same elements. This will give you <math>7 \cdot 8</math> elements, which is <math>56</math>. However, as stated above, we have overlap. Just count starting from <math>a+b - 15,14,13,4,5,11,6,10,7,9</math> all overlap once, which is <math>10</math>, thus <math>56 - 10 = 46</math> cases in this first case. Note that <math>12</math> wasn't included because again, if <math>c+d = 24</math>, <math>c</math> and <math>d</math> cannot be <math>12</math>.
+Let's say our four elements in our subset are <math>a,b,c,d</math>. We have two cases.
-Our second case is when <math>a+b = 16</math> and <math>b+c = 24</math>. Here, one element <math>(b)</math> is included twice in both equations. We can easily see that <math>a, b, c</math> will never equal each other. Furthermore, there are 17 choices for <math>d (20 - 3</math> included elements<math>)</math> for each <math>b</math>. Listing out the possible <math>b</math>s, we go from <math>15,14,13,11,10,9,7,6,5,4</math>. Do not include <math>8</math> or <math>12</math> because if they are included, then <math>a/c</math> will be the same as <math>b</math>, which is restricted. There are <math>10 </math>options there, and since <math>10 \cdot 17 = 170</math>, you would think there are <math>170</math> cases and we are done.
+First, we can have where two distinct elements sum to <math>16</math> and two other distinct elements sum to <math>24</math>. Basically, one way of representing this is having <math>a+b = 16</math> and <math>c+d = 24</math>. The order of the elements / the element letters themselves don't matter since they are all on equal grounds at the start. List out possibilities for <math>a+b</math> <math>(\text{i.e. } 1+15, 2+14, 3+13 \text{ etc.})</math> but don't include <math>8+8</math> because those are the same elements and that is restricted. Then list out the possibilities for <math>c+d \text{ }(\text{i.e. } 4+20, 5+19, 6+18, \text{ etc.})</math> but again don't list <math>12+12</math> because they are the same elements. This will give you <math>7 \cdot 8</math> elements, which is <math>56</math>. However, as stated above, we have overlap. Just count starting from <math>a+b - 15,14,13,4,5,11,6,10,7,9</math> all overlap once, which is <math>10</math>, thus <math>56 - 10 = 46</math> cases in this first case. Note that <math>12</math> wasn't included because again, if <math>c+d = 24</math>, <math>c</math> and <math>d</math> cannot be <math>12</math>.
-That's the tricky part about this problem - not the computation itself, but how easily sillies can be made. This is because, if <math>a+b = 16</math> and <math>b+c = 24</math>, notice that <math>c-a = 8</math>. That means that if <math>b-d</math> is also <math>8</math>, then we have a double-counted set. Starting with <math>b=15</math>, we have <math>15, 14, 13, 11, 10, 9 (</math>where <math>d</math> is <math>7, 6, 5, 3, 2, 1)</math>. That means there are <math>6</math> double-counted cases.
+Our second case is when <math>a+b = 16</math> and <math>b+c = 24</math>. Here, one element <math>(b)</math> is included twice in both equations. We can easily see that <math>a, b, c</math> will never equal each other. Furthermore, there are 17 choices for <math>d (20 - 3</math> included elements<math>)</math> for each <math>b</math>. Listing out the possible <math>b</math>s, we go from <math>15,14,13,11,10,9,7,6,5,4</math>. Do not include <math>8</math> or <math>12</math> because if they are included, then <math>a/c</math> will be the same as <math>b</math>, which is restricted. There are <math>10 </math>options there, and since <math>10 \cdot 17 = 170</math>, you would think there are <math>170</math> cases and we are done. That's the tricky part about this problem - not the computation itself, but how easily sillies can be made. This is because, if <math>a+b = 16</math> and <math>b+c = 24</math>, notice that <math>c-a = 8</math>. That means that if <math>b-d</math> is also <math>8</math>, then we have a double-counted set. Starting with <math>b=15</math>, we have <math>15, 14, 13, 11, 10, 9</math> (where <math>d</math> is <math>7, 6, 5, 3, 2, 1)</math>. That means there are <math>6</math> double-counted cases.
-Adding these up, we get <math>46+170-6 = \boxed{210}</math>
+Adding these up, we get <math>46+170-6 = \boxed{210}.</math>
 ~IronicNinja
-~<math>\LaTeX</math><math>ed</math> by AlcBoy1729
+~<math>\LaTeX</math> by AlcBoy1729
+~Formatted by ojaswupadhyay
 <cmath></cmath>
 Again if anyone wants to format this better feel free, I was just lazy.

2018 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search