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

Difference between revisions of "1993 AIME Problems/Problem 8"

(→‎See also)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
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>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1993|num-b=7|num-a=9}}
 
{{AIME box|year=1993|num-b=7|num-a=9}}

Revision as of 00:06, 7 December 2009

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

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=33012"