Problem
COM-B2-M01-P020 Strong Intersection Through an Average
Let \(A_1,\ldots,A_m\) be subsets of an \(n\)-element set, each of size at least \(r\). Prove that there exist two sets \(A_i,A_j\) such that
\[\left|A_i\cap A_j\right|\ge \frac{r(mr-n)}{n(m-1)}.\]
Let \(d(x)\) be the number of sets containing \(x\). Count the sum of all pairwise intersections.
The sum of all pairwise intersection sizes is \(\sum_x\binom{d(x)}2\), because each element \(x\) contributes to pairs of sets containing it. Since \(\sum d(x)\ge mr\), convexity gives
\[\sum_x\binom{d(x)}2\ge n\binom{mr/n}{2}=\frac{mr(mr-n)}{2n}.\]
There are \(\binom m2\) pairs of sets. Hence the average pairwise intersection size is at least
\[\frac{\frac{mr(mr-n)}{2n}}{\binom m2}=\frac{r(mr-n)}{n(m-1)}.\]
Therefore one intersection is at least this average.
A strong closing problem: double counting, convexity, and averaging in one argument.