1993 AIME Problems/Problem 8

Problem

Let $S\,$ be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of $S\,$ so that the union of the two subsets is $S\,$ ? The order of selection does not matter; for example, the pair of subsets $\{a, c\}\,$ , $\{b, c, d, e, f\}\,$ represents the same selection as the pair $\{b, c, d, e, f\}\,$ , $\{a, c\}\,$ .

Solution

Call the two subsets $m$ and $n$ . For each of the elements in $S$ , we can assign it to either $m$ , $n$ , or both. This gives us $3^6$ 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 $m$ and $n$ contain all $6$ elements of $S$ . So our final answer is then $\frac {3^6 - 1}{2} + 1 = \boxed{365}$

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

Page

Toolbox

Search

1993 AIME Problems/Problem 8

Problem

Solution

See also