Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 AIME I Problems/Problem 9"
m (→‎Solutions)
 
(18 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Find the number of four-element subsets of <math>\{1,2,3,4,\dots, 20\}</math> with the property that two distinct elements of a subset have a sum of <math>16</math>, and two distinct elements of a subset have a sum of <math>24</math>. For example, <math>\{3,5,13,19\}</math> and <math>\{6,10,20,18\}</math> are two such subsets.
 
Find the number of four-element subsets of <math>\{1,2,3,4,\dots, 20\}</math> with the property that two distinct elements of a subset have a sum of <math>16</math>, and two distinct elements of a subset have a sum of <math>24</math>. For example, <math>\{3,5,13,19\}</math> and <math>\{6,10,20,18\}</math> are two such subsets.
−
 
−
==Solutions==
 
  
 
==Solution 1==
 
==Solution 1==
Line 14: Line 12:
  
 
Case 2.
 
Case 2.
−
We can look for solutions by listing possible <math>a</math> values and filling in the blanks. Start with <math>a=4</math>, as that is the minimum. We find <math>\{4, 12, 20, ?\}</math>, and likewise up to <math>a=15</math>. But we can't have <math>a=8</math> or <math>a=12</math> because <math>a=b</math> or <math>a=c</math>, respectively! Now, it would seem like there are <math>10</math> values for <math>a</math> and <math>17</math> unique values for each <math>?</math>, giving a total of <math>170</math>, 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 <math>6</math>. That's <math>164</math> for Case 2.
+
We can look for solutions by listing possible <math>a</math> values and filling in the blanks. Start with <math>a=4</math>, as that is the minimum. We find <math>\{4, 12, 20, ?\}</math>, and likewise up to <math>a=15</math>. But we can't have <math>a=8</math> or <math>a=12</math> because <math>a=b</math> or <math>a=c</math>, respectively! Now, it would seem like there are <math>10</math> values for <math>a</math> and <math>17</math> unique values for each <math>?</math>, giving a total of <math>170</math>, but that is once again not true because there are some repeated values!
 +
There are two cases of overcounting:
 +
 
 +
case 1) (5,11,13,19) & (5.11.19.13)
 +
 
 +
The same is for (6,10,14,18) and (7,9,15,17)
 +
 
 +
case 2) those that have the same b and c values
 +
 
 +
this case includes:
 +
 
 +
(1,15,9,7) and (7,9,15,1)
 +
 
 +
(2,14,10,6) and (6,10,14,2)
 +
 
 +
(3,13,11,5) and (5,11,13,3)
 +
 
 +
So we need to subtract 6 overcounts.
 +
So, that's <math>164</math> for Case 2.
  
 
Total gives <math>\boxed{210}</math>.
 
Total gives <math>\boxed{210}</math>.
Line 21: Line 37:
  
 
==Solution 2==
 
==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, if anyone wants to format is 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. Note that the order of the elements / the element letters themselves don't matter since they are all on equal grounds at the start.
  
−
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 (i.e., 1+15, 2+14, 3+13 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 (i.e. 4+20, 5+19, 6+18, etc.) but again don't list 12+12 because they are the same elements. This will give you 7*8 elements, which is 56. However, like above stated, 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 include 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 bs, 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*17 = 170, you would think there are 170 cases and we are done.
+
<math>\textrm{Case } 1 \textrm{:}</math> <math>a+b = 16</math> and <math>c+d = 24</math>.  
  
−
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 also is 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.
+
List out possibilities for <math>a+b</math> <math>(\text{i.e. } 1+15, 2+14, 3+13 \text{ etc.})</math> but don't list <math>8+8</math> because those are the same elements and that is restricted.  
  
−
Adding these up, we get <math>46+170-6 = \boxed{210}</math>
+
Then list out the possibilities for <math>c+d \text{ }(\text{i.e. } 4+20, 5+19, 6+18, \text{ etc.})</math> but 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</math>.  <math>15,14,13,11,10,9,7,6,5,4</math> all overlap once, which is <math>10</math>, thus <math>56 - 10 = 46</math> cases in this 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>.
 +
 
 +
 
 +
<math>\textrm{Case } 2 \textrm{:}</math> <math>a+b = 16</math> and <math>b+c = 24</math>.
 +
 
 +
Here, <math>b</math> is included 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</math> (<math>20 - 3</math> included elements) 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 thus <math>10 \cdot 17 = 170</math>. But, note that if <math>d = b+8</math>, <math>a+d = a+b+8 = 24</math>, and so 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. Thus <math>170 - 6 = 164</math> cases in this case.
 +
 
 +
Adding these up, we get <math>46+164 = \boxed{210}.</math>
  
 
~IronicNinja
 
~IronicNinja
 +
~<math>\LaTeX</math> by AlcBoy1729
 +
~Formatted by ojaswupadhyay and phoenixfire
  
−
Again if anyone wants to format this better feel free, I was just lazy.
+
==Solution 3 (Official MAA)==
−
 
+
There are two types of <math>\{a,b,c,d\} \subseteq \{1,2,3,4\dots,20\}</math> that have the needed property. There is either an assignment of distinct values for <math>a,\,b,\,c,</math> and <math>d</math> such that <math>a+b=16</math> and <math>c+d=24</math> or an assignment such that <math>a+b=16</math> and <math>a+c=24.</math> These two types are mutually exclusive because <math>c+d=24</math> and <math>a+c=24</math> imply that <math>a=d.</math> For the first type, there are <math>7</math> choices for <math>\{a,b\},</math> namely <math>\{1,15\},\,\{2,14\},\,\{3,13\},\,\{4,12\},\,\{5,11\},\,\{6,10\},</math> and <math>\{7,9\},</math> and there are <math>8</math> choices for <math>\{c,d\},</math> namely <math>\{4,20\},\,\{5,19\},\,\{6,18\},\,\{7,17\},\,\{8,16\},\,\{9,15\},\{10,14\},</math> and <math>\{11,13\}.</math> Thus a four-element subset of the first type can be formed by taking the union of one of <math>7</math> two-element subsets with one of <math>8</math> two-element subsets as long as these two subsets are disjoint. There are <math>10</math> such pairings that are not disjoint out of the <math>7\cdot 8=56</math> pairings, so there are <math>56-10=46</math> subsets of the first type.
−
== Solution 0 ==
 
  
−
This code works:
+
For subsets of the second type, there are <math>10</math> choices for the value of <math>a</math> <math>(4,\,5,\,6,\,7,\,9,\,10,\,11,\,13,\,14,\,15)</math> such that <math>b=16-a</math> and <math>c=24-a</math> can be two other elements of the subset. Note that in each of these cases, <math>c-b=(24-a)-(16-a)=8.</math> For each of these, there are <math>20-3=17</math> other values that can be chosen for the element <math>d</math> in the subset. But <math>10\cdot 17=170</math> counts some subsets more than once. In particular, a subset is counted twice if <math>b+d=24</math> or <math>c+d=16</math>. In such cases either <math>d=a+8</math> or <math>d=a-8</math>. There are exactly <math>6</math> subsets where the role of <math>a</math> can be played by two different elements of the set. They are <math>\{1,7,9,15\},\,\{2,6,10,14\},\,\{3,5,11,13\},\,\{5,11,13,19\},\,\{6,10,14,18\},</math> and <math>\{7,9,15,17\}</math>. Thus there are <math>170-6=164</math> subsets of the second type.
−
  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;
 
  
−
==See Also==
+
In all, there are <math>46+164=210</math> subsets with the required property.
 
{{AIME box|year=2018|n=I|num-b=8|num-a=10}}
 
{{AIME box|year=2018|n=I|num-b=8|num-a=10}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 23:32, 5 February 2022

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.

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! There are two cases of overcounting:

case 1) (5,11,13,19) & (5.11.19.13)

The same is for (6,10,14,18) and (7,9,15,17)

case 2) those that have the same b and c values

this case includes:

(1,15,9,7) and (7,9,15,1)

(2,14,10,6) and (6,10,14,2)

(3,13,11,5) and (5,11,13,3)

So we need to subtract 6 overcounts. So, that's $164$ for Case 2.

Total gives $\boxed{210}$.

-expiLnCalc

Solution 2

Let's say our four elements in our subset are $a,b,c,d$. We have two cases. Note that the order of the elements / the element letters themselves don't matter since they are all on equal grounds at the start.


$\textrm{Case } 1 \textrm{:}$ $a+b = 16$ and $c+d = 24$.

List out possibilities for $a+b$ $(\text{i.e. } 1+15, 2+14, 3+13 \text{ etc.})$ but don't list $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 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,11,10,9,7,6,5,4$ all overlap once, which is $10$, thus $56 - 10 = 46$ cases in this case. Note that $12$ wasn't included because again, if $c+d = 24$, $c$ and $d$ cannot be $12$.


$\textrm{Case } 2 \textrm{:}$ $a+b = 16$ and $b+c = 24$.

Here, $b$ is included 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 thus $10 \cdot 17 = 170$. But, note that if $d = b+8$, $a+d = a+b+8 = 24$, and so 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. Thus $170 - 6 = 164$ cases in this case.

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

~IronicNinja ~$\LaTeX$ by AlcBoy1729 ~Formatted by ojaswupadhyay and phoenixfire

Solution 3 (Official MAA)

There are two types of $\{a,b,c,d\} \subseteq \{1,2,3,4\dots,20\}$ that have the needed property. There is either an assignment of distinct values for $a,\,b,\,c,$ and $d$ such that $a+b=16$ and $c+d=24$ or an assignment such that $a+b=16$ and $a+c=24.$ These two types are mutually exclusive because $c+d=24$ and $a+c=24$ imply that $a=d.$ For the first type, there are $7$ choices for $\{a,b\},$ namely $\{1,15\},\,\{2,14\},\,\{3,13\},\,\{4,12\},\,\{5,11\},\,\{6,10\},$ and $\{7,9\},$ and there are $8$ choices for $\{c,d\},$ namely $\{4,20\},\,\{5,19\},\,\{6,18\},\,\{7,17\},\,\{8,16\},\,\{9,15\},\{10,14\},$ and $\{11,13\}.$ Thus a four-element subset of the first type can be formed by taking the union of one of $7$ two-element subsets with one of $8$ two-element subsets as long as these two subsets are disjoint. There are $10$ such pairings that are not disjoint out of the $7\cdot 8=56$ pairings, so there are $56-10=46$ subsets of the first type.

For subsets of the second type, there are $10$ choices for the value of $a$ $(4,\,5,\,6,\,7,\,9,\,10,\,11,\,13,\,14,\,15)$ such that $b=16-a$ and $c=24-a$ can be two other elements of the subset. Note that in each of these cases, $c-b=(24-a)-(16-a)=8.$ For each of these, there are $20-3=17$ other values that can be chosen for the element $d$ in the subset. But $10\cdot 17=170$ counts some subsets more than once. In particular, a subset is counted twice if $b+d=24$ or $c+d=16$. In such cases either $d=a+8$ or $d=a-8$. There are exactly $6$ subsets where the role of $a$ can be played by two different elements of the set. They are $\{1,7,9,15\},\,\{2,6,10,14\},\,\{3,5,11,13\},\,\{5,11,13,19\},\,\{6,10,14,18\},$ and $\{7,9,15,17\}$. Thus there are $170-6=164$ subsets of the second type.

In all, there are $46+164=210$ subsets with the required property.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_9&oldid=171007"