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

Revision as of 13:01, 24 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 \cap B$ , $Y = A \backslash \left( A \cap B \right)$ , $Z = B \backslash \left( A \cap B \right)$ , $W = \Omega \backslash \left( A \cup B \right)$ .

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

Therefore, we have the following three cases: (1) $|Y| = 0$ and $|Z| \neq 0$ , (2) $|Z| = 0$ and $|Y| \neq 0$ , (3) $|Y| = |Z| = 0$ . Next, we analyze each of these cases, separately.

Case 1: $|Y| = 0$ and $|Z| \neq 0$ .

In this case, to count the number of solutions, we do the complementary counting.

First, we count the number of solutions that satisfy $|Y| = 0$ .

Hence, each number in $\Omega$ falls into exactly one out of these three sets: $X$ , $Z$ , $W$ . Following from the rule of product, the number of solutions is $3^5$ .

Second, we count the number of solutions that satisfy $|Y| = 0$ and $|Z| = 0$ .

Hence, each number in $\Omega$ falls into exactly one out of these two sets: $X$ , $W$ . Following from the rule of product, the number of solutions is $2^5$ .

Therefore, following from the complementary counting, the number of solutions in this case is equal to the number of solutions that satisfy $|Y| = 0$ minus the number of solutions that satisfy $|Y| = 0$ and $|Z| = 0$ , i.e., $3^5 - 2^5$ .

Case 2: $|Z| = 0$ and $|Y| \neq 0$ .

This case is symmetric to Case 1. Therefore, the number of solutions in this case is the same as the number of solutions in Case 1, i.e., $3^5 - 2^5$ .

Case 3: $|Y| = 0$ and $|Z| = 0$ .

Recall that this is one part of our analysis in Case 1. Hence, the number solutions in this case is $2^5$ .

By putting all cases together, following from the rule of sum, the total number of solutions is equal to

$\begin{align*} \left( 3^5 - 2^5 \right) + \left( 3^5 - 2^5 \right) + 2^5 & = 2 \cdot 3^5 - 2^5 \\ & = \boxed{454} . \end{align*}$

~ Steven Chen (www.professorchenedu.com)

Solution 3 (Casework Bash)

By the Principle of Inclusion-Exclusion (abbreviated PIE), we have $|A \cup B|=|A|+|B|-|A \cap B|,$ from which we rewrite the given equation as $|A| \cdot |B| = |A \cap B| \cdot \left(|A|+|B|-|A \cap B|\right).$ Rearranging and applying Simon's Favorite Factoring Trick give $\begin{align*} |A| \cdot |B| &= |A \cap B|\cdot|A| + |A \cap B|\cdot|B| - |A \cap B|^2 \\ |A| \cdot |B| - |A \cap B|\cdot|A| - |A \cap B|\cdot|B| &= - |A \cap B|^2 \\ \left(|A| - |A \cap B|\right)\cdot\left(|B| - |A \cap B|\right) &=0. \end{align*}$ We will use casework on the value of $|A \cap B|:$ $\begin{array}{c|c|l} & & \\ [-2.25ex] \boldsymbol{|A \cap B|} & \textbf{Equation} & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{Condition} \\ [0.5ex] \hline & & \\ [-2ex] 0 & |A|\cdot|B|=0 & \text{either } |A|=0, |B|=0, \text{ or both} \\ 1 & \left(|A|-1\right)\cdot\left(|B|-1\right)=0 & \text{either } |A|=1, |B|=1, \text{ or both} \\ 2 & \left(|A|-2\right)\cdot\left(|B|-2\right)=0 & \text{either } |A|=2, |B|=2, \text{ or both} \\ 3 & \left(|A|-3\right)\cdot\left(|B|-3\right)=0 & \text{either } |A|=3, |B|=3, \text{ or both} \\ 4 & \left(|A|-4\right)\cdot\left(|B|-4\right)=0 & \text{either } |A|=4, |B|=4, \text{ or both} \\ 5 & \left(|A|-5\right)\cdot\left(|B|-5\right)=0 & \text{either } |A|=5, |B|=5, \text{ or both} \\ [0.5ex] \end{array}$

... Steps will be written very soon ...

Two solutions follow from here:

Solution 3.1 (Combinatorial Identities)

Solution 3.2 (Hard Calculations)

SOLUTION IN PROGRESS. NO EDIT PLEASE--A MILLION THANKS!

~MRENTHUSIASM

@@ Line 96: / Line 96: @@
 & \left(|A|-5\right)\cdot\left(|B|-5\right)=0 & \text{either } |A|=5, |B|=5, \text{ or both}  \\  [0.5ex]
 \end{array}</cmath>
+... Steps will be written very soon ...
+Two solutions follow from here:
+===Solution 3.1 (Combinatorial Identities)===
+===Solution 3.2 (Hard Calculations)===
 <b>SOLUTION IN PROGRESS. NO EDIT PLEASE--A MILLION THANKS!</b>

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

Page

Toolbox

Search