Difference between revisions of "1993 AIME Problems/Problem 8"
(→Solution 5) |
(→Solution 5) |
||
Line 116: | Line 116: | ||
~vaporwave | ~vaporwave | ||
− | ~MrThinker(LaTeX improvements) | + | ~MrThinker (LaTeX improvements) |
== See also == | == See also == | ||
{{AIME box|year=1993|num-b=7|num-a=9}} | {{AIME box|year=1993|num-b=7|num-a=9}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 22:25, 13 October 2022
Contents
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 1 (Overcounting)
Call the two subsets and
For each of the elements in
we can assign it to either
or both. This gives us
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
and
contain all
elements of
So our final answer is then
Solution 2 (Overcounting)
Given one of subsets with
elements, the other also has
possibilities; this is because it must contain all of the "missing"
elements and thus has a choice over the remaining
We want
by the Binomial Theorem. But the order of the sets doesn't matter, so we get
Solution 3 (Recursion)
For all nonnegative integers let
be the number of elements in
and
be the number of unordered pairs
of subsets of
for which
We wish to find
Without the loss of generality, let the elements of be
Based on the value of
we construct the following table:
Note that for all
each unordered pair of the
-element set contributes three unordered pairs to the
-element set, as the element
can be added to either or both of the subsets. The only exception is that the unordered pair of identical subsets of the
-element set, namely
only contributes two unordered pairs to the
-element set. The table above shows this relationship between the
-element set and the
-element set.
Together, the recursive formula for is
Two solutions follow from here:
Solution 3.1 (Recursive Formula)
We evaluate recursively:
~MRENTHUSIASM
Solution 3.2 (Explicit Formula)
For all we have
which resembles the result in Solutions 1 and 2. The answer is
As note that
holds for
too. Therefore, this formula is true for all nonnegative integers
~MRENTHUSIASM
Solution 4 (Bash)
If we wanted to, we could use casework, being very careful not to double count cases. Let's first figure out what cases we need to look at. The notation I will be using is which implies that we pick
numbers for the first set which then the second set can have
numbers.
Clearly:
However notice that many of the cases are double counted as direction does not matter, e.g.
is the same as
Get rid of those cases so we are just left with:
Now we start computing,
is just
case,
is just
cases,
is just
cases, and
is just
cases (If you have trouble understanding this, write down the six letters and then try to understand what
really means.). Now what you can do is continue on this same pattern like Solution 2 does, and then use simple symmetry to figure out the double counted cases. However, the purpose of this solution is to bash out the double counted cases, so we will do exactly that.
One quick thing though. We have a double counted case with the as choosing ABC and DEF is the same thing as choosing DEF and then ABC. There are
cases of this.
For computing we use the same process as before. We have
(Note, the
comes from
), and for
we have
and then for
we just have
(there is no double counted case since ABCDEF, ABCDEF is only counted once).
Summing case by case, we have
Disclaimer: This is a terrible solution, it should only be done as practice for casework bashing and never should be done on a real AIME.
~Tost (Solution)
~MRENTHUSIASM (Reformatting)
Solution 5
We can perform casework based on the number of overlapping elements. If no elements overlap, there is way to choose the overlapping elements, and
ways to distribute the remaining elements--each element can go in one subset or the other. We must also divide by
because the order of the subsets does not matter. Proceeding similarly for the other cases, our sum is
(Note that we have to be especially careful with the last case, as it does not follow the pattern of the other cases.) Adding these up gives a total of
~vaporwave
~MrThinker (LaTeX improvements)
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.