2023 AIME II Problem 11

Below is the professionally curated solution for Problem 11 of the 2023 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2023 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:subsetsgraph theorycasework

Difficulty rating: 3060

11.

Find the number of collections of 1616 distinct subsets of {1,2,3,4,5}\{1, 2, 3, 4, 5\} with the property that for any two subsets XX and YY in the collection, XY.X \cap Y \neq \emptyset.

Solution:

The 3232 subsets split into 1616 complementary pairs {X,Xc},\{X, X^{\mathsf{c}}\}, and no collection can contain both members of a pair (they are disjoint). A collection of 1616 pairwise-intersecting subsets must therefore contain exactly one member of every pair; in particular it contains {1,2,3,4,5}\{1,2,3,4,5\} and not .\emptyset.

If some singleton {x}\{x\} is chosen, every member must meet {x},\{x\}, i.e. contain x.x. Exactly one set in each complementary pair contains x,x, so the collection must be exactly the 1616 subsets containing x:x: this gives 55 collections. Otherwise no singleton is chosen, so all five 44-element sets are in the collection. Any two 33-element subsets of a 55-element set intersect, a 44-element set is disjoint only from its complement, and a chosen 22-element set and a chosen 33-element set are disjoint only if they are complements, which cannot both be chosen. So the only remaining condition is that the chosen 22-element sets pairwise intersect.

Viewing 22-element sets as edges of K5,K_5, a pairwise-intersecting collection of edges either has all edges through one common vertex or is a triangle. The number of such edge families is: the empty family (11), triangles ((53)=10\binom{5}{3} = 10), and nonempty families within a star, 5(241)10=655(2^4 - 1) - 10 = 65 (subtracting the 1010 single edges counted at both endpoints). That is 1+10+65=761 + 10 + 65 = 76 collections, for a total of 5+76=81.5 + 76 = 81.

← Problem 10Full ExamProblem 12

Problem 11 in Other Years