Question

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

Answer

Solution:

Let $a = |A|,$ $b = |B|,$ and $i = |A \cap B|,$ so $|A \cup B| = a + b - i.$ The condition $ab = i(a + b - i)$ rearranges to $ab - ia - ib + i^2 = (a - i)(b - i) = 0,$ so $|A \cap B| = |A|$ or $|A \cap B| = |B|.$ Since $A \cap B$ is a subset of each, that means $A \subseteq B$ or $B \subseteq A.$

For pairs with $A \subseteq B,$ each of the $5$ elements independently lies in neither set, in $B$ only, or in both: $3^5 = 243$ pairs. Likewise $243$ pairs satisfy $B \subseteq A,$ and the pairs counted twice are exactly those with $A = B,$ of which there are $2^5 = 32.$ The answer is $243 + 243 - 32 = 454.$

2021 AIME II Problem 6

Solution:

Problem 6 in Other Years