Высшая проба 2020, 11 класс, задача 7
( баллов) Даны подмножеств -элементного множества: . Обозначим через число элементов множества . Рассмотрим неравенство
в котором индексы пробегают все значения от до , то есть в сумме всего слагаемых.
а) Докажите это неравенство при .
б) Докажите это неравенство при произвольном натуральном .
Ответ
Решение. Посчитаем левую часть иным образом. Для каждого элемента множества из элементов посчитаем, в какое количество пересечений троек он входит, и просуммируем эти количества по всем элементам. Легко видеть, что если элемент входит в множеств, то он входит ровно в пересечений троек множеств (в качестве первого множества тройки годятся множеств, в качестве второй и третьей - тоже ). Таким образом, левая часть это . Теперь заметим, что
так как обе суммы подсчитывают двумя способами одну и ту же величину: количество пар (множество; элемент множества). Итого, надо доказать:
Последнее неравенство равносильно неравенству между средним кубическим и средним арифметическим:
Замечание. Это одна из лемм (Lemma ) в статье на arXiv.