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

Latest revision as of 01:02, 29 January 2024

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|$ . Substituting into the equation and factoring, we get that $(|A| - |A \cap B|)(|B| - |A \cap B|) = 0$ , so therefore $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 have 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 (Principle of Inclusion-Exclusion)

By the Principle of Inclusion-Exclusion (abbreviated as 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*}$ from which at least one of the following is true:

$|A|=|A \cap B|$

$|B|=|A \cap B|$

Let $|A \cap B|=k.$ For each value of $k\in\{0,1,2,3,4,5\},$ we will use PIE to count the ordered pairs $(A,B):$

Suppose $|A|=k.$ There are $\binom{5}{k}$ ways to choose the elements for $A.$ These $k$ elements must also appear in $B.$ Next, there are $2^{5-k}$ ways to add any number of the remaining $5-k$ elements to $B$ (Each element has $2$ options: in $B$ or not in $B.$ ). There are $\binom{5}{k}2^{5-k}$ ordered pairs for $|A|=k.$ Similarly, there are $\binom{5}{k}2^{5-k}$ ordered pairs for $|B|=k.$

To fix the overcount, we subtract the number of ordered pairs that are counted twice, in which $|A|=|B|=k.$ There are $\binom{5}{k}$ such ordered pairs.

Therefore, there are $2\binom{5}{k}2^{5-k}-\binom{5}{k}$ ordered pairs for $|A \cap B|=k.$

Two solutions follow from here:

Solution 3.1 (Binomial Theorem)

The answer is $\begin{align*} \sum_{k=0}^{5}\left[2\binom{5}{k}2^{5-k}-\binom{5}{k}\right] &= 2\sum_{k=0}^{5}\binom{5}{k}2^{5-k}-\sum_{k=0}^{5}\binom{5}{k} \\ &=2(2+1)^5-(1+1)^5 \\ &=2(243)-32 \\ &=\boxed{454}. \end{align*}$ ~MRENTHUSIASM

Solution 3.2 (Bash)

The answer is $\begin{align*} &\hspace{5.125mm}\sum_{k=0}^{5}\left[2\binom{5}{k}2^{5-k}-\binom{5}{k}\right] \\ &=\left[2\binom{5}{0}2^{5-0}-\binom{5}{0}\right] + \left[2\binom{5}{1}2^{5-1}-\binom{5}{1}\right] + \left[2\binom{5}{2}2^{5-2}-\binom{5}{2}\right] + \left[2\binom{5}{3}2^{5-3}-\binom{5}{3}\right] + \left[2\binom{5}{4}2^{5-4}-\binom{5}{4}\right] + \left[2\binom{5}{5}2^{5-5}-\binom{5}{5}\right] \\ &=\left[2\left(1\right)2^5-1\right] + \left[2\left(5\right)2^4-5\right] + \left[2\left(10\right)2^3-10\right] + \left[2\left(10\right)2^2-10\right] + \left[2\left(5\right)2^1-5\right] + \left[2\left(1\right)2^0-1\right] \\ &=63+155+150+70+15+1 \\ &=\boxed{454}. \end{align*}$ ~MRENTHUSIASM

Solution 4 (Simple Bash)

Proceed with Solution 1 to get $(|A| - |A \cap B|)(|B| - |A \cap B|) = 0$ . WLOG, assume $|A| = |A \cap B|$ . Thus, $A \subseteq B$ .

Since $A \subseteq B$ , if $|B| = n$ , there are $2^n$ possible sets $A$ , and there are also ${5 \choose n}$ ways of choosing such $B$ .

Therefore, the number of possible pairs of sets $(A, B)$ is

$\sum_{k=0}^{5} 2^n {5 \choose n}$

We can compute this manually since it's only from $k=0$ to $5$ , and computing gives us $243$ . We can double this result for $B \subseteq A$ , and we get $2(243) = 486$ .

However, we have double counted the cases where $A$ and $B$ are the same sets. There are $32$ possible such cases, so we subtract $32$ from $486$ to get $\boxed{454}$ .

~ adam_zheng

Video Solution by Interstigation

https://youtu.be/jEghPVjyHoc

~Interstigation

Video Solution & Set Theory Review

https://youtu.be/3vcLujj74RM

~MathProblemSolvingSkills.com

@@ Line 1: / Line 1: @@
-These problems will not be available until the 2021 AIME II is released on Thursday, March 25, 2021.
+==Problem==
+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 1==
+By PIE, <math>|A|+|B|-|A \cap B| = |A \cup B|</math>. Substituting into the equation and factoring, we get that <math>(|A| - |A \cap B|)(|B| - |A \cap B|) = 0</math>, so therefore <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 have 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
+==Solution 2==
+We denote <math>\Omega = \left\{ 1 , 2 , 3 , 4 , 5 \right\}</math>.
+We denote <math>X = A \cap B</math>, <math>Y = A \backslash \left( A \cap B \right)</math>, <math>Z = B \backslash \left( A \cap B \right)</math>, <math>W = \Omega \backslash \left( A \cup 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>
+Therefore, we have the following three cases: (1) <math>|Y| = 0</math> and <math>|Z| \neq 0</math>, (2) <math>|Z| = 0</math> and <math>|Y| \neq 0</math>, (3) <math>|Y| = |Z| = 0</math>.
+Next, we analyze each of these cases, separately.
+Case 1: <math>|Y| = 0</math> and <math>|Z| \neq 0</math>.
+In this case, to count the number of solutions, we do the complementary counting.
+First, we count the number of solutions that satisfy <math>|Y| = 0</math>.
+Hence, each number in <math>\Omega</math> falls into exactly one out of these three sets: <math>X</math>, <math>Z</math>, <math>W</math>.
+Following from the rule of product, the number of solutions is <math>3^5</math>.
+Second, we count the number of solutions that satisfy <math>|Y| = 0</math> and <math>|Z| = 0</math>.
+Hence, each number in <math>\Omega</math> falls into exactly one out of these two sets: <math>X</math>, <math>W</math>.
+Following from the rule of product, the number of solutions is <math>2^5</math>.
+Therefore, following from the complementary counting, the number of solutions in this case is equal to the number of solutions that satisfy <math>|Y| = 0</math> minus the number of solutions that satisfy <math>|Y| = 0</math> and <math>|Z| = 0</math>, i.e., <math>3^5 - 2^5</math>.
+Case 2: <math>|Z| = 0</math> and <math>|Y| \neq 0</math>.
+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., <math>3^5 - 2^5</math>.
+Case 3: <math>|Y| = 0</math> and <math>|Z| = 0</math>.
+Recall that this is one part of our analysis in Case 1. Hence, the number solutions in this case is <math>2^5</math>.
+By putting all cases together, following from the rule of sum, the total number of solutions is equal to
+<cmath>
+\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*}
+</cmath>
+~ Steven Chen (www.professorchenedu.com)
+==Solution 3 (Principle of Inclusion-Exclusion)==
+By the <b>Principle of Inclusion-Exclusion (abbreviated as PIE)</b>, we have <math>|A \cup B|=|A|+|B|-|A \cap B|,</math> from which we rewrite the given equation as <cmath>|A| \cdot |B| = |A \cap B| \cdot \left(|A|+|B|-|A \cap B|\right).</cmath>
+Rearranging and applying Simon's Favorite Factoring Trick give
+<cmath>\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*}</cmath>
+from which at least one of the following is true:
+* <math>|A|=|A \cap B|</math>
+* <math>|B|=|A \cap B|</math>
+Let <math>|A \cap B|=k.</math> For each value of <math>k\in\{0,1,2,3,4,5\},</math> we will use PIE to count the ordered pairs <math>(A,B):</math>
+Suppose <math>|A|=k.</math> There are <math>\binom{5}{k}</math> ways to choose the elements for <math>A.</math> These <math>k</math> elements must also appear in <math>B.</math> Next, there are <math>2^{5-k}</math> ways to add any number of the remaining <math>5-k</math> elements to <math>B</math> (Each element has <math>2</math> options: in <math>B</math> or not in <math>B.</math>). There are <math>\binom{5}{k}2^{5-k}</math> ordered pairs for <math>|A|=k.</math> Similarly, there are <math>\binom{5}{k}2^{5-k}</math> ordered pairs for <math>|B|=k.</math>
+To fix the overcount, we subtract the number of ordered pairs that are counted twice, in which <math>|A|=|B|=k.</math> There are <math>\binom{5}{k}</math> such ordered pairs.
+Therefore, there are <cmath>2\binom{5}{k}2^{5-k}-\binom{5}{k}</cmath> ordered pairs for <math>|A \cap B|=k.</math>
+Two solutions follow from here:
+===Solution 3.1 (Binomial Theorem)===
+The answer is
+<cmath>\begin{align*}
+\sum_{k=0}^{5}\left[2\binom{5}{k}2^{5-k}-\binom{5}{k}\right] &= 2\sum_{k=0}^{5}\binom{5}{k}2^{5-k}-\sum_{k=0}^{5}\binom{5}{k} \\
+&=2(2+1)^5-(1+1)^5 \\
+&=2(243)-32 \\
+&=\boxed{454}.
+\end{align*}</cmath>
+~MRENTHUSIASM
+===Solution 3.2 (Bash)===
+The answer is
+<cmath>\begin{align*}
+&\hspace{5.125mm}\sum_{k=0}^{5}\left[2\binom{5}{k}2^{5-k}-\binom{5}{k}\right] \\
+&=\left[2\binom{5}{0}2^{5-0}-\binom{5}{0}\right] + \left[2\binom{5}{1}2^{5-1}-\binom{5}{1}\right] + \left[2\binom{5}{2}2^{5-2}-\binom{5}{2}\right] + \left[2\binom{5}{3}2^{5-3}-\binom{5}{3}\right] + \left[2\binom{5}{4}2^{5-4}-\binom{5}{4}\right] + \left[2\binom{5}{5}2^{5-5}-\binom{5}{5}\right] \\
+&=\left[2\left(1\right)2^5-1\right] + \left[2\left(5\right)2^4-5\right] + \left[2\left(10\right)2^3-10\right] + \left[2\left(10\right)2^2-10\right] + \left[2\left(5\right)2^1-5\right] + \left[2\left(1\right)2^0-1\right] \\
+&=63+155+150+70+15+1 \\
+&=\boxed{454}.
+\end{align*}</cmath>
+~MRENTHUSIASM
+==Solution 4 (Simple Bash)==
+Proceed with Solution 1 to get <math>(|A| - |A \cap B|)(|B| - |A \cap B|) = 0</math>. WLOG, assume <math>|A| = |A \cap B|</math>. Thus, <math>A \subseteq B</math>.
+Since <math>A \subseteq B</math>, if <math>|B| = n</math>, there are <math>2^n</math> possible sets <math>A</math>, and there are also <math>{5 \choose n}</math> ways of choosing such <math>B</math>.
+Therefore, the number of possible pairs of sets <math>(A, B)</math> is
+<cmath>
+\sum_{k=0}^{5} 2^n {5 \choose n}
+</cmath>
+We can compute this manually since it's only from <math>k=0</math> to <math>5</math>, and computing gives us <math>243</math>. We can double this result for <math>B \subseteq A</math>, and we get <math>2(243) = 486</math>.
+However, we have double counted the cases where <math>A</math> and <math>B</math> are the same sets. There are <math>32</math> possible such cases, so we subtract <math>32</math> from <math>486</math> to get <math>\boxed{454}</math>.
+~ adam_zheng
+==Video Solution by Interstigation==
+https://youtu.be/jEghPVjyHoc
+~Interstigation
+==Video Solution & Set Theory Review==
+https://youtu.be/3vcLujj74RM
+~MathProblemSolvingSkills.com
+==See Also==
+{{AIME box|year=2021|n=II|num-b=5|num-a=7}}
+{{MAA Notice}}

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