Тема КОМБИНАТОРИКА

Графы и турниры → .11 Раскраски графов

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Графы и турниры

Индукция в графах и теорема Турана

Турниры в терминах графов и не только (считаем игры и очки)

Лемма о рукопожатиях

Считаем рёбра

Простой путь, Гамильтонов путь, Гамильтонов цикл

Подвешивание, ранжирование, упорядочивание в графах

Деревья и остовные деревья

Двудольные графы и переформулировки к ним

Связность и связные подграфы (клики)

Паросочетания и лемма Холла

Формула Эйлера для графов и многогранников

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#85754Максимум баллов за задание: 7

Ребра полного графа с $n$ вершинами покрашены в несколько цветов таким образом, что каждый цвет встречается не более $n− 2$ раз. Докажите, что есть три вершины, все ребра между которыми покрашены в различные цвета.

Подсказки к задаче

Подсказка 1

Часто полезно рассматривать что-то крайнее. Выберете какой-нибудь параметр и исследуйте его.

Подсказка 2

Рассмотрите вершину из которой выходит наибольшее количество одноцветных ребер. Посмотрите на связи между соседями этой вершины.

Показать доказательство

Рассмотрим вершину $A,$ из которой выходит наибольшее количество одноцветных рёбер. Пусть они $1$ цвета. Пусть соединена первых цветом с $A1,A2,...,Ax.$ Рассмотрим оставшиеся $n− x− 1$ вершину, с которыми $A$ соединена другими цветами. Любая из этих вершин соединена со всеми $Ai$ либо первым цветом, либо тем же цветом, которым она соединена с $A.$ Однако заметим, что между $A$ и вершинами, отличными от $Ai$ может быть не более $n− 2− x$ рёбер первого цвета, поскольку есть $x$ рёбер $AAi.$ Но, как мы выяснили ранее, имеется $n− x− 1 >n − 2 − x$ вершина, не соединённая с $A$ первым цветом. Значит, среди них есть одна вершина $X$ такая, что цвет всех рёбер $XAi$ совпадает с цветом ребра $XA.$ Но тогда из $X$ выходит $x +1$ одноцветное ребро, это противоречит выбору $A.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#49160Максимум баллов за задание: 7

Вершины правильного $100$ -угольника раскрашены случайным образом в два цвета: $50$ вершин — в белый цвет, $50$ — в черный. Докажите, что можно разбить все вершины на $25$ групп по $4$ вершины так, чтобы в каждой группе было по две вершины каждого цвета, и вершины каждой группы являлись вершинами некоторого прямоугольника.

Источники: Курчатов-2018, 11.2 (см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

Давайте подумаем, а как красивым способом получить прямоугольники? И для чего нам условие правильности 100угольника, что с ним можно сделать?

Подсказка 2

Можно провести 50 диаметров этого 100угольника, тогда любые два диаметра являются диагоналями некоторого прямоугольника! Значит, нам нужно разбить их на 25 пар, в каждой из которых поровну черных и белых концов! Что для этого достаточно?

Подсказка 3

Чтобы полностью чёрных диаметров было столько же, сколько и полностью белых. Осталось лишь подумать, почему это так)

Показать доказательство

Проведём $50$ диаметров нашего $100$ -угольника. Нам требуется разбить их на пары так, чтобы в каждой паре было поровну чёрных и белых вершин. Для этого необходимо и достаточно, чтобы полностью чёрных диаметров было столько же, сколько и полностью белых. Действительно, если это не так, то один из таких диаметров останется без пары — ему не подойдут разноцветные диаметры. Если же это так, то мы бьём все одноцветные на пары с одинаковыми цветами, после чего остальных останется чётное количество (всего диаметров $50$ ) и их можно разбить как угодно.

Итак, почему же чёрных диаметров столько же, сколько и белых? Каждый разноцветный диаметр содержит одинаковое количество белого и чёрного цвета, потому на одноцветные приходится также равное количество этих двух цветов (изначально каждого по $50$ ). Но раз так, то количество чёрных и белых диаметров будет одинаковым, чтобы они содержали равное количество разных цветов, что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 23#77993Максимум баллов за задание: 7

На острове рыцарей и лжецов некоторые жители дружат друг с другом. Рыцари всегда говорят правду, а лжецы всегда лгут. Каждый житель сказал: “Среди моих друзей рыцарей больше, чем лжецов”. Докажите, что пар друзей одного вида не менее половины.

Источники: Лига открытий - 2018

Подсказки к задаче

Подсказка 1

Проверьте, что даёт нам сказанная всеми фраза в зависимости от того, кто её сказал — рыцарь или лжец.

Подсказка 2

Получается, у каждого рыцаря друзей-рыцарей не больше, чем друзей-лжецов, а у каждого лжеца друзей-лжецов не меньше, чем друзей рыцарей.
Давайте переведем это на язык графов: пусть люди — это вершинки, раскрашенные в два цвета (т.е. один цвет — рыцарь, другой — лжец), а дружба между ними — ребро. Тогда что можно теперь сказать?

Подсказка 3

У каждого человека смежных одноцветных ребер больше, чем разноцветных. Поймите, что во всем графе тогда тоже одноцветных ребер больше, чем разноцветных, а это мы и хотели доказать)

Показать доказательство

Заметим, что у каждого рыцаря больше друзей рыцарей, а у каждого лжеца друзей лжецов хотя бы столько же, сколько и друзей рыцарей. Тогда в соответствующем графе (вершины первого цвета — рыцари, второго цвета — лжецы, ребро проводится, если два жителя дружат) у каждой вершины одноцветных рёбер не меньше, чем разноцветных. Значит, если их все просуммировать, то и всего одноцветных рёбер не меньше, чем разноцветных.

Ошибка.
Попробуйте повторить позже

Задача 24#36854Максимум баллов за задание: 7

В городе Джентльвилле живут $15$ джентльменов, любые двое из которых либо дружат, либо враждуют. В какой-то момент каждый джентльмен попросил каждого из своих друзей послать открытку ненависти каждому из своих врагов (джентльмен $A$ просит джентльмена $B$ послать открытку всем врагам джентльмена $B$ ). Каждый из джентльменов выполнил все просьбы; при этом он посылал каждому из своих врагов такое количество открыток, сколько раз его об этом просили. Какое наибольшее количество открыток могло быть послано?

Источники: ИТМО-2016, отборочный тур, 11 класс (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1!

1) Так, было бы здорово оценить количество открыток как-то, в зависимости от количества друзей, чтобы попробовать посчитать максимум..... Например, если у человека друзей будет х, а врагов соответственно 14-х, то сколько открыток он пошлет?

Подсказка 2!

2) Так, хорошо, х(14-х)! Нужно понять, где это выражение принимает максимум, и проверить, получится ли наш максимум достигнуть... Было тут у нас какое-то утверждение про степени вершин в графе... Хм...

Подсказка 3!

3) Ага, вот оно! Лемма о рукопожатиях! Теперь идейно задачу решили, осталось только немного разобраться, как все же получить новый максимум!

Показать ответ и решение

Рассмотрим полный граф на $15$ вершинах, вершинами которого являются джентльмены, а рёбрами — отношения между ними. Покрасим между двумя вершинами в белый цвет, если джентльмены, соответствующие этим вершинам дружат. А чёрные ребра будут символизировать вражду между людьми.

Оценка.

Пусть у джентльмена с номером $n$ ( $1≤ n≤ 15$ ) ровно $xn$ друзей и $14 − xn$ врагов ( $xn ∈ ℕ∪ {0}$ ). Тогда он отправил ровно $xn⋅(14− xn)$ писем. Это выражение является квадратным трёхчленом, наибольшее значение которого достигается при $xn =7$ и равно $49.$ Тогда число отправленных всеми джентльменами писем не превосходит $49 ⋅15.$

Покажем, что отправить ровно $49⋅15$ писем невозможно по лемме о рукопожатиях (в любом графе количество вершин нечётной степени чётно). Действительно, в таком случае у каждого джентльмена должно быть $7$ друзей и $7$ врагов. Рассмотрим подграф из всех вершин и только белых рёбер. В этом подграфе количество рёбер (количество пар друзей среди джентльменов) равно половине от суммы степеней вершин (у каждого по $7$ друзей, но одну и ту же пару считаем дважды), то есть $7⋅125.$ Противоречие с тем, что это число должно быть целым.

Пример.

Покажем, что отправить $49 ⋅15− 1= 734$ писем возможно. Достаточно построить “чёрный” подграф: нужно соединить каждого джентльмена с тремя следующими — получим однородный граф степени $6,$ затем останется соединить каких-то $7$ подряд с джентльменами, которые идут на $7$ позиций позже по кругу. То есть $1 ⇐ ⇒ 8,2 ⇐⇒ 9...7 ⇐⇒ 14.$ Тогда степени первых $14$ -и вершин станут равны $7,$ а у $15$ -й она останется равной $6.$

Ответ:

$734$

Ошибка.
Попробуйте повторить позже

Задача 25#88474Максимум баллов за задание: 7

Некоторый граф правильно раскрашен в $k$ цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех $k$ цветов ровно по одному разу.

Подсказки к задаче

Подсказка 1

Сказано, что нельзя в k-1 цвет, а вы попробуйте перекрашивать. Когда могут возникнуть трудности?

Подсказка 2

Перекрашивать произвольные вершины в разные цвета немного странно. Хочется определенные вершины перекрашивать в определенный цвет. Попробуйте вершины цвета 2 перекрасить в цвет 1?

Подсказка 3

Нам не удастся перекрасить все вершины по условию. Что нам могло помешать? Только вершины цвета 2, соединенные соединенные с цветом 1. А что, если поочередно так сделать со всеми цветами?

Подсказка 4

Теперь все вершины соединены с цветом на 1 меньше, либо их перекрасили. Найдите тут искомую цепочку.

Показать доказательство

Цвета, в которые покрашен граф, занумеруем от $1$ до $k.$ Те вершины цвета $2,$ которые не соседствуют ни с какими вершинами цвета $1,$ перекрасим в цвет $1.$ Новая раскраска будет правильной, поэтому в ней $k$ цветов. Значит, какие-то вершины цвета $2$ не перекрашены и потому соседствуют с вершинами цвета $1.$ Аналогично, вершины цвета $3,$ которые не соседствуют с вершинами цвета $2,$ перекрасим в цвет $2,$ и т. д. вплоть до последнего цвета.

После этого рассмотрим какую-либо вершину цвета $k.$ Она не перекрашена, и потому соседствует с вершиной цвета $k− 1.$ Эта вершина тоже не перекрашена, так как иначе её первоначальный цвет был бы $k,$ и она не могла бы соседствовать с вершиной того же цвета. Раз вершина не перекрашена, то она соседствует с вершиной цвета $k− 2,$ и т. д. Продолжая этот процесс, построим путь из вершин $k$ цветов, которые не были перекрашены.

Предыдущая подтема

Следующая подтема