Ошибка.
Попробуйте повторить позже
В классе учеников. В течение сентября каждый из них несколько раз ходил в бассейн; никто не ходил дважды в один день. Первого октября выяснилось, что все количества посещений бассейна у учеников различны. Более того, для любых двух из них обязательно был день, когда первый из них был в бассейне, а второй — нет, и день, когда, наоборот, второй из них был в бассейне, а первый — нет. Найдите наибольшее возможное значение В сентябре дней.
Для каждого натурального обозначим Каждому ученику сопоставим множество всех дней, когда он ходил в бассейн (это будет подмножество в ). Итого, мы получили набор из (согласно условию, непустых) подмножеств в Условие равносильно тому, что во всех подмножествах разные количества элементов, и ни одно из них не содержится в другом; назовём такой набор подмножеств хорошим. Таким образом, нам нужно найти максимальное число множеств в хорошем семействе подмножеств в
Докажем сначала, что такой набор не может содержать больше множеств. Это очевидно, если в наборе есть -элементное подмножество, так как оно содержит любое другое. Значит, можно считать, что множества в наборе могут состоять лишь из элементов (и их не больше ). Пусть в хорошем наборе есть -элементное множество и -элементное множество Так как не содержится в они не пересекаются. Тогда любое другое подмножество в либо содержит либо содержится в Значит, в этом случае хороший набор состоит лишь из двух подмножеств. Наконец, если в наборе нет или -элементного подмножества, то в нём уже не более множеств, что и требовалось.
Осталось предъявить пример хорошего набора из подмножеств в Для этого покажем индукцией по что существует хороший набор подмножеств в причём содержит элемент. В базовом случае годятся подмножества и
Пусть для некоторого уже построен требуемый хороший набор подмножеств в Тогда требуемый хороший набор подмножеств в можно построить так. Положим при эти множества содержат элементов соответственно. Наконец, положим и Нетрудно проверить, что они образуют требуемый хороший набор. Тем самым переход индукции доказан.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!