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