Задача
COM-B2-M01-P011 Два множества с большим пересечением
#11
★★★☆☆ Уровень 3 из 5
Есть \(8\) трёхэлементных подмножеств \(5\)-элементного множества. Докажите, что два из них имеют не менее двух общих элементов.
Суммируйте размеры попарных пересечений через элементы.
Пусть \(d_i\) — число подмножеств, содержащих \(i\)-й элемент. Тогда \(\sum d_i=24\). Сумма размеров всех попарных пересечений равна \(\sum_{i=1}^5\binom{d_i}{2}\). При фиксированной сумме \(24\) эта величина минимальна при распределении \(5,5,5,5,4\), и равна \(46\). Если бы все попарные пересечения имели размер не больше \(1\), сумма была бы не больше \(\binom82=28\). Противоречие.
Для сильных учеников можно отдельно доказать минимальность через перенос \(a,b\mapsto a-1,b+1\).