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"
(My solution was wrong, so I use Adunakhor's.)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
Let's select the subsets <math>A</math> and <math>B</math> in that order such that <math>|A|\leq |B|</math>. Now there are 6 cases: <math>A</math> has no elements, <math>A</math> has <math>1</math> element, ... , and <math>A</math> has <math>6</math> elements.
+
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>
−
 
 
−
If <math>A</math> has no elements, then <math>B</math> must have all of the elements, and there is only <math>1</math> way to do that.
 
−
 
 
−
If <math>A</math> has one element, then <math>B</math> must have the other 5 elements, and it can include <math>A</math>'s element or not. There are <math>2</math> ways to do that.
 
−
 
 
−
If <math>A</math> has two elements, then <math>B</math> must have the other 4 elements, and it can include <math>A</math>'s elements or not. There are <math>4</math> ways to do that.
 
−
 
 
−
If <math>A</math> has three elements, then <math>B</math> must have the other 3 elements, and it can include <math>A</math>'s elements or not. There are <math>8</math> ways to do that.
 
−
 
 
−
If <math>A</math> has four elements, then <math>B</math> 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 (<math>a_1</math>, <math>a_2</math>, <math>a_3</math>, and <math>a_4</math>). There are <math>\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=11</math>.
 
−
 
 
−
If <math>A</math> has five elements, then <math>B</math> 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 (<math>a_1</math>, <math>a_2</math>, <math>a_3</math>, <math>a_4</math>, or <math>a_5</math>). There are <math>\binom{5}{4}+\binom{5}{5}=6</math>.
 
−
 
 
−
If <math>A</math> has all six elements, then <math>B</math> must have all 6 elements, and there is only <math>1</math> way to do that.
 
−
 
 
−
<math>1+2+4+8+11+6+1=\boxed{033}</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 10:54, 28 February 2008

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