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 1

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}$

Solution 2

Given one of ${6 \choose k}$ subsets with $k$ elements, the other also has $2^k$ possibilities; this is because it must contain all of the "missing" $n - k$ elements and thus has a choice over the remaining $k$ . We want $\sum_{k = 0}^6 {6 \choose k}2^k = (2 + 1)^6 = 729$ by Binomial Theorem. But the order of the sets doesn't matter, so we get $\dfrac{729 - 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

Contents

Problem

Solution 1

Solution 2

See also