Задача
COM-B2-M01-P018 Обобщение на \(t+1\)-подмножества
Пусть выбрано \(m\) подмножеств размера \(k\) в \(n\)-элементном множестве. Известно, что любые два выбранных подмножества имеют не более \(t\) общих элементов. Докажите, что \(m\binom{k}{t+1}\le\binom{n}{t+1}\).
Считайте \((t+1)\)-элементные подмножества, лежащие внутри выбранных множеств.
Каждое выбранное \(k\)-элементное множество содержит \(\binom{k}{t+1}\) подмножеств размера \(t+1\), всего \(m\binom{k}{t+1}\) появлений. Но одно и то же \((t+1)\)-элементное подмножество не может лежать в двух выбранных множествах: тогда эти два множества имели бы как минимум \(t+1\) общих элементов, что запрещено. Всего \((t+1)\)-подмножеств исходного множества \(\binom{n}{t+1}\). Получаем неравенство.
Это сильная форма предыдущих задач и хороший финальный шаблон.