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