Difference between revisions of "2008 AMC 10A Problems/Problem 23"
m (added "solution" heading) |
(→Solution 1) |
||
| Line 6: | Line 6: | ||
==Solution== | ==Solution== | ||
===Solution 1=== | ===Solution 1=== | ||
| − | First choose the two letters to be repeated in each set. <math>\dbinom{5}{2}=10</math>. Now we have three remaining elements that we wish to place into two separate subsets. There are <math>2^3 = 8 </math> ways to do so (Do you see why? It's because each of the three remaining letters can be placed either into the first or second subset. Both of those subsets contain the two chosen elements, so their intersection is the two chosen elements). Unfortunately, we have over-counted (Take for example <math>S_{1} = \{a,b,c,d \}</math> and <math>S_{2} = \{a,b,e \}</math>). Notice how <math>S_{1}</math> and <math>S_{2}</math> are interchangeable. A simple division by two will fix this problem. Thus we have: | + | First, choose the two letters to be repeated in each set. <math>\dbinom{5}{2}=10</math>. Now we have three remaining elements that we wish to place into two separate subsets. There are <math>2^3 = 8 </math> ways to do so (Do you see why? It's because each of the three remaining letters can be placed either into the first or second subset. Both of those subsets contain the two chosen elements, so their intersection is the two chosen elements). Unfortunately, we have over-counted (Take for example <math>S_{1} = \{a,b,c,d \}</math> and <math>S_{2} = \{a,b,e \}</math>). Notice how <math>S_{1}</math> and <math>S_{2}</math> are interchangeable. A simple division by two will fix this problem. Thus we have: |
<math> \dfrac{10 \times 8}{2} = 40 \implies \boxed{\text{B}} </math> | <math> \dfrac{10 \times 8}{2} = 40 \implies \boxed{\text{B}} </math> | ||
Revision as of 19:33, 4 June 2021
Contents
Problem
Two subsets of the set 
are to be chosen so that their union is 
and their intersection contains exactly two elements. In how many ways can this be done, assuming that the order in which the subsets are chosen does not matter?
Solution
Solution 1
First, choose the two letters to be repeated in each set. 
. Now we have three remaining elements that we wish to place into two separate subsets. There are 
ways to do so (Do you see why? It's because each of the three remaining letters can be placed either into the first or second subset. Both of those subsets contain the two chosen elements, so their intersection is the two chosen elements). Unfortunately, we have over-counted (Take for example 
and 
). Notice how 
and 
are interchangeable. A simple division by two will fix this problem. Thus we have:
Solution 2
Another way of looking at this problem is to break it down into cases.
First, our two subsets can have 2 and 5 elements. The 5-element subset (aka the set) will contain the 2-element subset. There are ways to choose the 2-element subset. Thus, there are 
ways to create these sets.
Second, the subsets can have 3 and 4 elements. 
non-distinct elements. 
elements in the intersection. There are 
ways to choose the 3-element subset. For the 4-element subset, two of the elements must be the remaining elements (not in the 3-element subset). The other two have to be a subset of the 3-element subset. There are 
ways to choose these two elements, which means there are 3 ways to choose the 4-element subset. Therefore, there are 
ways to choose these sets.
This leads us to the answer:
Solution 3
We label the subsets subset 1 and subset 2. Suppose the first subset has 
elements where 
The second element has 
elements which the first subset does not contain (in order for the union to be the whole set). Additionally, the second set has 2 elements in common with the first subset. Therefore the number of ways to choose these sets is 
Computing for 
we have 
Divide by 2 for order to get 
Solution 4 (Stars And Bars)
There are ways to choose the 2 shared elements. We now must place the 3 remaining elements into the subsets. Using stars and bars, we can notate this as: IIIX=> 
. Thus, 
See also
| 2008 AMC 10A (Problems • Answer Key • Resources) | ||
| Preceded by Problem 22 |
Followed by Problem 24 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
| All AMC 10 Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
