Difference between revisions of "2021 AIME II Problems/Problem 6"
(→Problem) |
(→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | + | Since | |
+ | <math>|A|+|B|-|A \cap B| = |A \cup B|</math>, substituting gives us | ||
+ | \begin{align*} | ||
+ | |A| \cdot |B| &= |A \cap B|(|A| + |B| - |A \cap B|)\ | ||
+ | |A||B| - |A \cap B||A| - |A \cap B||B| + |A \cap B| &= 0\ | ||
+ | (|A| - |A \cap B|)(|B| - |A \cap B|) &= 0.\ | ||
+ | \end{align*}. | ||
+ | Therefore we need <math>A \subseteq B</math> or <math>B \subseteq A</math>. WLOG <math>A\subseteq B</math>, then for each element there are <math>3</math> possibilities, either it is in both <math>A</math> and <math>B</math>, it is in <math>B</math> but not <math>A</math>, or it is in neither <math>A</math> nor <math>B</math>. This gives us <math>3^{5}</math> possibilities, and we multiply by <math>2</math> since it could of also been the other way around. Now we need to subtract the overlaps where <math>A=B</math>, and this case has <math>2^{5}=32</math> ways that could happen. It is <math>32</math> because each number could be in the subset or it could not be in the subset. So the final answer is <math>2\cdot 3^5 - 2^5 = \boxed{454}</math>. | ||
+ | |||
+ | ~ math31415926535 | ||
==See also== | ==See also== | ||
{{AIME box|year=2021|n=II|num-b=5|num-a=7}} | {{AIME box|year=2021|n=II|num-b=5|num-a=7}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 14:24, 22 March 2021
Problem
For any finite set , let
denote the number of elements in
. FInd the number of ordered pairs
such that
and
are (not necessarily distinct) subsets of
that satisfy
Solution
Since
, substituting gives us
or
. WLOG
, then for each element there are
possibilities, either it is in both
and
, it is in
but not
, or it is in neither
nor
. This gives us
possibilities, and we multiply by
since it could of also been the other way around. Now we need to subtract the overlaps where
, and this case has
ways that could happen. It is
because each number could be in the subset or it could not be in the subset. So the final answer is
.
~ math31415926535
See also
2021 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
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.