Problem
COM-B2-M01-P017 Large Intersection Among Many Sets
#17
★★★★☆ Level 4 of 5
In a \(20\)-element set, \(30\) subsets of size \(6\) are chosen. Prove that two of them intersect in at least two elements.
Assume all intersections have size at most \(1\), and count pairs inside subsets.
If any two chosen subsets intersect in at most one element, then the same pair of elements cannot lie in two different subsets. Thus the total number of pair occurrences is at most \(\binom{20}{2}=190\). But each of the \(30\) subsets of size \(6\) contains \(\binom62=15\) pairs, for \(450\) occurrences. Contradiction. Hence two subsets have at least two common elements.
The numbers are chosen so that the contradiction is very visible.