Problem
COM-B2-M01-P011 Two Sets with Large Intersection
#11
★★★☆☆ Level 3 of 5
There are \(8\) three-element subsets of a \(5\)-element set. Prove that two of them have at least two common elements.
Sum pairwise intersection sizes through elements.
Let \(d_i\) be the number of subsets containing the \(i\)-th element. Then \(\sum d_i=24\). The sum of all pairwise intersection sizes is \(\sum_{i=1}^5\binom{d_i}{2}\). With fixed sum \(24\), this is minimised by the balanced distribution \(5,5,5,5,4\), giving \(46\). If every pairwise intersection had size at most \(1\), the sum would be at most \(\binom82=28\). Contradiction.
For stronger students, prove the balancing minimum separately via shifting \(a,b\mapsto a-1,b+1\).