Difference between revisions of "1993 AIME Problems/Problem 8"
(→Solution) |
|||
| Line 2: | Line 2: | ||
Let <math>S\,</math> be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of <math>S\,</math> so that the union of the two subsets is <math>S\,</math>? The order of selection does not matter; for example, the pair of subsets <math>\{a, c\}\,</math>, <math>\{b, c, d, e, f\}\,</math> represents the same selection as the pair <math>\{b, c, d, e, f\}\,</math>, <math>\{a, c\}\,</math>. | Let <math>S\,</math> be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of <math>S\,</math> so that the union of the two subsets is <math>S\,</math>? The order of selection does not matter; for example, the pair of subsets <math>\{a, c\}\,</math>, <math>\{b, c, d, e, f\}\,</math> represents the same selection as the pair <math>\{b, c, d, e, f\}\,</math>, <math>\{a, c\}\,</math>. | ||
| − | == Solution == | + | == Solution 1 == |
Call the two subsets <math>m</math> and <math>n</math>. For each of the elements in <math>S</math>, we can assign it to either <math>m</math>, <math>n</math>, or both. This gives us <math>3^6</math> possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both <math>m</math> and <math>n</math> contain all <math>6</math> elements of <math>S</math>. So our final answer is then <math>\frac {3^6 - 1}{2} + 1 = \boxed{365}</math> | Call the two subsets <math>m</math> and <math>n</math>. For each of the elements in <math>S</math>, we can assign it to either <math>m</math>, <math>n</math>, or both. This gives us <math>3^6</math> possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both <math>m</math> and <math>n</math> contain all <math>6</math> elements of <math>S</math>. So our final answer is then <math>\frac {3^6 - 1}{2} + 1 = \boxed{365}</math> | ||
| + | |||
| + | == Solution 2 == | ||
| + | |||
| + | Given one of <math>{6 \choose k}</math> subsets with <math>k</math> elements, the other also has <math>2^k</math> possibilities; this is because it must contain all of the "missing" <math>n - k</math> elements and thus has a choice over the remaining <math>k</math>. We want <math>\sum_{k = 0}^6 {6 \choose k}2^k = (2 + 1)^6 = 729</math> by Binomial Theorem. But the order of the sets doesn't matter, so we get <math>\dfrac{729 - 1}{2} + 1 = \boxed{365}</math>. | ||
== See also == | == See also == | ||
{{AIME box|year=1993|num-b=7|num-a=9}} | {{AIME box|year=1993|num-b=7|num-a=9}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 17:48, 9 July 2013
Contents
Problem
Let 
be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of so that the union of the two subsets is ? The order of selection does not matter; for example, the pair of subsets 
, 
represents the same selection as the pair , .
Solution 1
Call the two subsets 
and 
. For each of the elements in 
, we can assign it to either , , or both. This gives us 
possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both and contain all 
elements of . So our final answer is then 
Solution 2
Given one of 
subsets with 
elements, the other also has 
possibilities; this is because it must contain all of the "missing" 
elements and thus has a choice over the remaining . We want 
by Binomial Theorem. But the order of the sets doesn't matter, so we get 
.
See also
| 1993 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 7 |
Followed by Problem 9 | |
| 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. 
