Difference between revisions of "1993 AIME Problems/Problem 8"
m |
|||
| 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. |
| + | |||
| + | 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:50, 28 February 2008
Problem
Let 
be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of so that the union of the two subsets is ? The order of selection does not matter; for example, the pair of subsets 
, 
represents the same selection as the pair , .
Solution
Let's select the subsets 
and 
in that order such that 
. Now there are 6 cases: has no elements, has 
element, ... , and has 
elements.
If has no elements, then must have all of the elements, and there is only way to do that.
If has one element, then must have the other 5 elements, and it can include 's element or not. There are 
ways to do that.
If has two elements, then must have the other 4 elements, and it can include 's elements or not. There are 
ways to do that.
If has three elements, then must have the other 3 elements, and it can include 's elements or not. There are 
ways to do that.
If has four elements, then 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 (
, 
, 
, and 
). There are 
.
If has five elements, then 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 (, , , , or 
). There are 
.
If has all six elements, then must have all 6 elements, and there is only way to do that.
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 | ||
