Difference between revisions of "2021 AIME II Problems/Problem 6"
(→Solution) |
(→Solution 1) |
||
| Line 2: | Line 2: | ||
For any finite set <math>S</math>, let <math>|S|</math> denote the number of elements in <math>S</math>. FInd the number of ordered pairs <math>(A,B)</math> such that <math>A</math> and <math>B</math> are (not necessarily distinct) subsets of <math>\{1,2,3,4,5\}</math> that satisfy<cmath>|A| \cdot |B| = |A \cap B| \cdot |A \cup B|</cmath> | For any finite set <math>S</math>, let <math>|S|</math> denote the number of elements in <math>S</math>. FInd the number of ordered pairs <math>(A,B)</math> such that <math>A</math> and <math>B</math> are (not necessarily distinct) subsets of <math>\{1,2,3,4,5\}</math> that satisfy<cmath>|A| \cdot |B| = |A \cap B| \cdot |A \cup B|</cmath> | ||
| − | ==Solution== | + | ==Solution 1== |
By PIE, <math>|A|+|B|-|A \cap B| = |A \cup B|</math>, and after some algebra you see that 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>. | By PIE, <math>|A|+|B|-|A \cap B| = |A \cup B|</math>, and after some algebra you see that 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>. | ||
Revision as of 20:11, 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![\[|A| \cdot |B| = |A \cap B| \cdot |A \cup B|\]](http://latex.artofproblemsolving.com/a/8/c/a8c5056f13bbfd71412164ca53b71c92395e5812.png)
Solution 1
By PIE, 
, and after some algebra you see that we need 
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. 
