Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 AIME II Problems/Problem 6"

(→‎Solution)
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Since
+
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>.
−
<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
 
~ math31415926535

Revision as of 14:34, 22 March 2021

Problem

For any finite set $S$, let $|S|$ denote the number of elements in $S$. FInd the number of ordered pairs $(A,B)$ such that $A$ and $B$ are (not necessarily distinct) subsets of $\{1,2,3,4,5\}$ that satisfy\[|A| \cdot |B| = |A \cap B| \cdot |A \cup B|\]

Solution

By PIE, $|A|+|B|-|A \cap B| = |A \cup B|$, and after some algebra you see that we need $A \subseteq B$ or $B \subseteq A$. WLOG $A\subseteq B$, then for each element there are $3$ possibilities, either it is in both $A$ and $B$, it is in $B$ but not $A$, or it is in neither $A$ nor $B$. This gives us $3^{5}$ possibilities, and we multiply by $2$ since it could of also been the other way around. Now we need to subtract the overlaps where $A=B$, and this case has $2^{5}=32$ ways that could happen. It is $32$ because each number could be in the subset or it could not be in the subset. So the final answer is $2\cdot 3^5 - 2^5 = \boxed{454}$.

~ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_6&oldid=149703"