Соответствия, сравнения, количества

Сначала покажем, что можно выбрать не более чем подмножество из элементов, чтобы условие выполнялось. Для достаточно взять все -элементные подмножества и условие будет выполнено, а таких множеств поэтому формула выполняется.

Для подмножество такого размера единственно, поэтому формула снова верна.

Для докажем по индукции. База индукции тогда а при таких формула выполняется.

Для использования перехода — будем считать, что — это не обязательно числа, а именно -ый элемент по возрастанию элементы в множестве. Далее рассмотрим максимальное количество -элементных подмножеств элементного множества таких, что для любых таких подмножеств, одно их них состоит из наименьших элементов объединения. Рассмотрим объединение всех этих подмножеств. Если объединение не совпадает с множеством то можно рассмотреть объединение этих подмножеств (в нем не более элемента), для которого выполнено предположение индукции, но тогда этих подмножеств было

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

Далее удалим из набора подмножество Теперь объединение всех подмножеств не совпадает с иначе бы опять встретилось подмножество Опять-таки по предположению индукции подмножеств станет Тогда изначально с подмножество было не более

Теперь построим пример на подмножество множества чтобы для любых из них, одного содержало наименьших элементов объединения этих подмножеств.

Рассмотрим все подмножества вида где Тогда и так как то содержит наименьшие элементов объединения.