Высшая проба 2020, 9-10 классы, задача 7
( баллов) Даны подмножеств -элементного множества: . Обозначим через число элементов множества . Рассмотрим неравенство
в котором индексы , , пробегают все значения от до , то есть в сумме всего слагаемых.
а) Докажите это неравенство при .
б) Докажите это неравенство при произвольном натуральном .
Доказательство. Посчитаем левую часть иным образом. Для каждого элемента множества из элементов посчитаем, в какое количество пересечений троек он входит, и просуммируем эти количества по всем элементам. Легко видеть, что если элемент входит в множеств, то он входит ровно в пересечений троек множеств (в качестве первого множества тройки годятся множеств, в качестве второй и третьей - тоже ). Таким образом, левая часть это . Теперь заметим, что , так как обе суммы подсчитывают двумя способами одну и ту же величину: количество пар (множество; элемент множества). Итого, надо доказать:
Последнее неравенство равносильно неравенству между средним кубическим и средним арифметическим:
Замечание. Это одна из лемм (Lemma ) в статье https://arxiv.org/pdf/1808.08363.pdf
− Решение задачи в частном случае.
− Решение основано на неправильной формуле включения-исключения.
± Сведено к неравенству n2· b3 ()3..
Баллы 0 - -. ∓ +/2 ± +. + 1 0 0 2 4 8 10 12 12 2 0 0 2 5 8 10 15 15 3 0 0 2 5 8 10 15 15 4 0 0 2 5 10 15 20 20 5 0 0 4 8 16 25 32 32 6 0 0 4 8 16 22 28 28 7a 0 0 2 5 8 10 15 15 7б 0 0 4 8 13 20 25 25.