Задача
COM-B2-M01-P006 Элемент во многих множествах
#6
★★★☆☆ Уровень 3 из 5
Дано \(18\) подмножеств \(10\)-элементного множества, каждое имеет не меньше \(4\) элементов. Докажите, что некоторый элемент входит хотя бы в \(8\) подмножеств.
Посчитайте инцидентности \((x,A)\).
Число пар \((x,A)\), где \(x\in A\), не меньше \(18\cdot4=72\). Эти пары распределены между \(10\) элементами. Среднее число множеств на элемент не меньше \(7.2\), значит некоторый элемент входит хотя бы в \(8\) множеств.
Простая, но уже олимпиадная формулировка среднего.