Math Gold Medalist

Lor

2023 AIME II

Problem 11

Find the number of collections of $16$ distinct subsets of $\{1,2,3,4,5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \not= \emptyset.$

Important Ideas in Pigeonhole Principle

Casework

Priority: The Most Limited Case

Split subsets into 16 groups ( Each subset with its complement subset)

Consider number of subsets with 1 element in the collection.

Then consider number of subsets with 2 elements in the collection.

   Solution