Регион 11 класс

Для каждого натурального обозначим Каждому ученику сопоставим множество всех дней, когда он ходил в бассейн (это будет подмножество в ). Итого, мы получили набор из (согласно условию, непустых) подмножеств в Условие равносильно тому, что во всех подмножествах разные количества элементов, и ни одно из них не содержится в другом; назовём такой набор подмножеств хорошим. Таким образом, нам нужно найти максимальное число множеств в хорошем семействе подмножеств в

Докажем сначала, что такой набор не может содержать больше множеств. Это очевидно, если в наборе есть -элементное подмножество, так как оно содержит любое другое. Значит, можно считать, что множества в наборе могут состоять лишь из элементов (и их не больше ). Пусть в хорошем наборе есть -элементное множество и -элементное множество Так как не содержится в они не пересекаются. Тогда любое другое подмножество в либо содержит либо содержится в Значит, в этом случае хороший набор состоит лишь из двух подмножеств. Наконец, если в наборе нет или -элементного подмножества, то в нём уже не более множеств, что и требовалось.

Осталось предъявить пример хорошего набора из подмножеств в Для этого покажем индукцией по что существует хороший набор подмножеств в причём содержит элемент. В базовом случае годятся подмножества и

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