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
~ 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.