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