Problem
COM-B2-M01-P013 Almost Disjoint Blocks
#13
★★★★☆ Level 4 of 5
In an \(n\)-element set, \(m\) subsets of size \(k\) are chosen. Any two chosen subsets have at most one common element. Prove that \(m\binom{k}{2}\le\binom n2\).
Count pairs of elements lying inside a chosen subset.
Each chosen subset contains \(\binom{k}{2}\) pairs of elements, giving \(m\binom{k}{2}\) pair occurrences. But the same pair of elements cannot lie in two different chosen subsets; otherwise those two subsets would share at least two elements. The whole ground set has only \(\binom n2\) pairs. Therefore \(m\binom{k}{2}\le\binom n2\).
A classic scheme for block designs and linear hypergraphs.