ВсОШ 2019, 9 класс, задача 4
В лагерь приехали детей, каждый дружит ровно с другими детьми в лагере (дружба взаимна). Каждый ребенок носит футболку одного из семи цветов радуги, причем у любых двух друзей цвета различны. Вожатые потребовали, чтобы какие-нибудь дети (хотя бы один) надели футболки других цветов (из тех же семи). Опрос показал, что детей менять цвет не намерены. Докажите, что некоторые из остальных детей все же могут изменить цвета своих футболок так, чтобы по-прежнему у любых двух друзей цвета были различны.
(А. Магазинов)
Решение.
Перейдём к графу, вершины которого соответствуют детям, а рёбра - дружбам. Напомним, что раскраска вершин называется правильной, если цвета любых двух вершин, соединённые ребром, различны. Таким образом, граф правильно раскрашен в цветов, в нём выделено стабильных вершин, и требуется перекрасить часть остальных вершин так, чтобы раскраска осталась правильной. Предположим, что это невозможно. Пронумеруем цвета числами . Рассмотрим любые два цвета . Оставим в графе только вершины этих цветов и рёбра между ними; обозначим полученный граф через . Этот граф может распасться на несколько компонент связности; обозначим через их количество. Если , то в одной из компонент нет стабильных вершин; тогда можно изменить цвет каждой вершины в этой компоненте, заменив на и наоборот, и добиться требуемой альтернативной раскраски. Значит, при всех и . Заметим, что каждая компонента связности, содержащая вершин, содержит не менее
рёбер; значит, если в есть вершин, то количество рёбер в нём не меньше, чем , то есть . (∗) С другой стороны, нетрудно найти сумму всех чисел и сумму всех чисел . Действительно, в исходном графе вершин, и каждая из них участвует в графах вида ; поэтому . С другой стороны, в исходном графе рёбер, и каждое участвует ровно в одном графе ; поэтому . Но, поскольку пар цветов всего , неравенство (∗) влечёт , что не так для найденных значений. Значит, наше предположение было неверно, и требуемая перекраска возможна.