Высшая проба 2020, 8 класс, задача 6

Ответ: .

Предположим, есть набор, у которого меньше больших поднаборов. Тогда все наборы из гирь большие. В самом деле, пусть поднабор без гири с весом - не большой. Тогда . У множества шести гирь (всех кроме ) есть подмножеств. Эти подмножества разбиваются на пары с пустым пересечением, дающие в объединении все гири без . Тогда в каждой паре хотя бы одно множество весит не менее . То есть половина, , из этих подмножеств весит не менее . Тогда каждое множество из этой половины в объединении с дает вес не менее . Таким образом, мы нашли больших набора. Противоречие.

Итого, на данный момент мы нашли уже больших поднаборов: -элементный и все семь -элементных. Посмотрим, какие -элементные подмножества могут не давать большой поднабор.

Допустим, все гири без гирь , - не большой поднабор, и все без , - тоже не большой поднабор (разными буквами обозначены разные гири). Тогда, рассуждая аналогично предыдущему случаю, получаем, что у дополнения к , есть подмножеств, дающих в объединении с , большой поднабор. То же самое с , : у дополнения к , есть подмножеств, дающих в объединении с , большой поднабор. Рассмотрим объединение этих поднаборов и оценим его мощность. Если первое множество наборов это , второе - это , то . Действительно, набор в пересечении и включает в себя , , , , и число способов дополнить его несколькими из оставшихся трех - не более . Итого, больших поднаборов . Значит, не существует таких непересекающихся пар , и , , что их пятиэлементные дополнения - не большие наборы. Или же, для любых двух -элементных не больших наборов их -элементные дополнения пересекаются. Максимальное количество попарно пересекающихся -элементных подмножеств множества из элементов - . (В самом деле, пусть есть несколько попарно-пересекающихся пар элементов -элементного множества. Если все пары содержат некоторый один и тот же элемент, то пар не больше чем остальных элементов, то есть . Пусть никакой элемент не принадлежит всем парам. Рассмотрим две любые пары , и , . Должна найтись пара, не содержащая , но чтобы она пересекалась с первыми двумя она должна быть парой , . Тогда больше ни одной пары добавить нельзя, итого в этом случае пар не больше чем .) Отсюда существует хотя бы больших пятиэлементных поднабора. Складывая это количество с (число уже найденных больших поднаборов мощности ), получаем оценку на хотя бы поднабора.

Пример. Как видно из доказательства оценки, самая тяжелая гиря должна весить строго меньше строго больше . Возьмем ее вес равным , или что то же самое . Тогда если веса остальных гирь взять равными, они получаются по . Из поднаборов без первой гири подходит только содержащий все остальные. Из поднаборов с первой гирей подходят гирь (первая и четыре оставшихся), гирь (первая и пять оставшихся) и гирь (первая и все шесть оставшихся). Итого, больших поднаборов $1+\binom64+\binom65+\binom66=1+15+6+1=2