Задача
COM-B2-M01-P017 Большое пересечение среди многих множеств
#17
★★★★☆ Уровень 4 из 5
В \(20\)-элементном множестве выбрано \(30\) подмножеств размера \(6\). Докажите, что два из них пересекаются хотя бы по двум элементам.
Предположите, что все пересечения имеют размер не больше \(1\), и считайте пары внутри подмножеств.
Если любые два выбранных подмножества пересекаются не более чем по одному элементу, то одна и та же пара элементов не может лежать в двух разных подмножествах. Тогда всего появлений пар не больше \(\binom{20}{2}=190\). Но каждое из \(30\) подмножеств размера \(6\) содержит \(\binom62=15\) пар, всего \(450\) появлений. Противоречие. Значит, два подмножества имеют хотя бы два общих элемента.
Числа специально подобраны так, чтобы противоречие было заметным.