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