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