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"

(→‎See also)
(→‎Solution 2)
Line 8: Line 8:
  
 
==Solution 2==
 
==Solution 2==
 +
 +
We denote <math>\Omega = \left\{ 1 , 2 , 3 , 4 , 5 \right\}</math>.
 +
We denote <math>X = A \intersect B</math>, <math>Y = A \backslash \left( A \intersect B \right)</math>, <math>Z = B \backslash \left( A \intersect B \right)</math>, <math>W = \Omega \backslash \left( A \union B \right)</math>.
 +
 +
Therefore, <math>X \cup Y \cup Z \cup W = \Omega</math> and the intersection of any two out of sets <math>X</math>, <math>Y</math>, <math>Z</math>, <math>W</math> is an empty set.
 +
Therefore, <math>\left( X , Y , Z , W \right)</math> is a partition of <math>\Omega</math>.
 +
 +
Following from our definition of <math>X</math>, <math>Y</math>, <math>Z</math>, we have <math>A \cup B = X \cup Y \cup Z</math>.
 +
 +
Therefore, the equation
 +
 +
<cmath>
 +
|A| \cdot |B| = |A \cap B| \cdot |A \cup B|
 +
</cmath>
 +
 +
can be equivalently written as
 +
 +
<cmath>
 +
\left( | X | + | Y | \right) \left( | X | + | Z | \right)
 +
= | X | \left( | X | + | Y | + | Z | \right) .
 +
</cmath>
 +
 +
This equality can be simplified as
 +
 +
<cmath>
 +
| Y | \cdot | Z | = 0 .
 +
</cmath>
  
 
~ Steven Chen (www.professorchenedu.com)
 
~ Steven Chen (www.professorchenedu.com)

Revision as of 20:19, 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 1

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

Solution 2

We denote $\Omega = \left\{ 1 , 2 , 3 , 4 , 5 \right\}$. We denote $X = A \intersect B$ (Error compiling LaTeX. Unknown error_msg), $Y = A \backslash \left( A \intersect B \right)$ (Error compiling LaTeX. Unknown error_msg), $Z = B \backslash \left( A \intersect B \right)$ (Error compiling LaTeX. Unknown error_msg), $W = \Omega \backslash \left( A \union B \right)$ (Error compiling LaTeX. Unknown error_msg).

Therefore, $X \cup Y \cup Z \cup W = \Omega$ and the intersection of any two out of sets $X$, $Y$, $Z$, $W$ is an empty set. Therefore, $\left( X , Y , Z , W \right)$ is a partition of $\Omega$.

Following from our definition of $X$, $Y$, $Z$, we have $A \cup B = X \cup Y \cup Z$.

Therefore, the equation

\[|A| \cdot |B| = |A \cap B| \cdot |A \cup B|\]

can be equivalently written as

\[\left( | X | + | Y | \right) \left( | X | + | Z | \right) = | X | \left( | X | + | Y | + | Z | \right) .\]

This equality can be simplified as

\[| Y | \cdot | Z | = 0 .\]

~ Steven Chen (www.professorchenedu.com)

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=149861"