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