Задача
COM-B2-M01-P020 Сильное пересечение через среднее
Пусть \(A_1,\ldots,A_m\) — подмножества \(n\)-элементного множества, каждое размера не меньше \(r\). Докажите, что найдутся два множества \(A_i,A_j\), для которых
\[\left|A_i\cap A_j\right|\ge \frac{r(mr-n)}{n(m-1)}.\]
Пусть \(d(x)\) — число множеств, содержащих \(x\). Считайте сумму всех попарных пересечений.
Сумма размеров всех попарных пересечений равна \(\sum_x\binom{d(x)}2\), потому что каждый элемент \(x\) вносит вклад в пары множеств, которые его содержат. При \(\sum d(x)\ge mr\) выпуклость даёт
\[\sum_x\binom{d(x)}2\ge n\binom{mr/n}{2}=\frac{mr(mr-n)}{2n}.\]
Пар множеств всего \(\binom m2\). Значит, средний размер попарного пересечения не меньше
\[\frac{\frac{mr(mr-n)}{2n}}{\binom m2}=\frac{r(mr-n)}{n(m-1)}.\]
Следовательно, одно из пересечений не меньше этого среднего.
Сильная завершающая задача: двойной подсчёт, выпуклость и среднее в одной схеме.