2021 AIME II Problem 6

Attempt Problem 6 of the 2021 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2021 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

6.

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

Answer: 454
Concepts:subsetsfactoringinclusion-exclusion
Difficulty rating: 2440
Solution:

Let a=A,a = |A|, b=B,b = |B|, and i=AB,i = |A \cap B|, so AB=a+bi.|A \cup B| = a + b - i. The condition ab=i(a+bi)ab = i(a + b - i) rearranges to abiaib+i2=(ai)(bi)=0, \begin{aligned} &ab - ia - ib + i^2 \\ &= (a - i)(b - i) = 0, \end{aligned} so AB=A|A \cap B| = |A| or AB=B.|A \cap B| = |B|. Since ABA \cap B is a subset of each, that means ABA \subseteq B or BA.B \subseteq A.

For pairs with AB,A \subseteq B, each of the 55 elements independently lies in neither set, in BB only, or in both: 35=2433^5 = 243 pairs. Likewise 243243 pairs satisfy BA,B \subseteq A, and the pairs counted twice are exactly those with A=B,A = B, of which there are 25=32.2^5 = 32. The answer is 243+24332=454.243 + 243 - 32 = 454.

← Problem 5#5
Full Exam

Problem 6 in Other Years