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

1993 AIME Problems/Problem 8

Revision as of 09:50, 28 February 2008 by 1=2 (talk | contribs)

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

Let's select the subsets $A$ and $B$ in that order such that $|A|\leq |B|$. Now there are 6 cases: $A$ has no elements, $A$ has $1$ element, ... , and $A$ has $6$ elements.

If $A$ has no elements, then $B$ must have all of the elements, and there is only $1$ way to do that.

If $A$ has one element, then $B$ must have the other 5 elements, and it can include $A$'s element or not. There are $2$ ways to do that.

If $A$ has two elements, then $B$ must have the other 4 elements, and it can include $A$'s elements or not. There are $4$ ways to do that.

If $A$ has three elements, then $B$ must have the other 3 elements, and it can include $A$'s elements or not. There are $8$ ways to do that.

If $A$ has four elements, then $B$ must have the other two elements, but we need two more elements. So we need to compute the number of ways to select at least two different numbers from letters ($a_1$, $a_2$, $a_3$, and $a_4$). There are $\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=11$.

If $A$ has five elements, then $B$ must have the only other element, but we need four more elements. So we need to compute the number of ways to select at least four different numbers from letters ($a_1$, $a_2$, $a_3$, $a_4$, or $a_5$). There are $\binom{5}{4}+\binom{5}{5}=6$.

If $A$ has all six elements, then $B$ must have all 6 elements, and there is only $1$ way to do that.

$1+2+4+8+11+6+1=\boxed{033}$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_8&oldid=23641"