Задача
COM-B2-M01-P013 Почти непересекающиеся блоки
#13
★★★★☆ Уровень 4 из 5
В \(n\)-элементном множестве выбрано \(m\) подмножеств размера \(k\). Любые два выбранных подмножества имеют не более одного общего элемента. Докажите, что \(m\binom{k}{2}\le\binom n2\).
Считайте пары элементов, лежащие внутри выбранного подмножества.
Каждое выбранное подмножество содержит \(\binom{k}{2}\) пар элементов, всего \(m\binom{k}{2}\) появлений пар. Но одна и та же пара элементов не может лежать в двух разных выбранных подмножествах, иначе эти два подмножества имели бы как минимум два общих элемента. Всего пар элементов в исходном множестве \(\binom n2\). Следовательно, \(m\binom{k}{2}\le\binom n2\).
Классическая схема для блок-дизайнов и линейных гиперграфов.