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