Задание №149655: Задание 9.4

9.4. На олимпиаду приехало несколько участников из n > 1 регионов, некоторые из них дру-
жат (дружба всегда взаимна). Выяснилось, что для произвольной рассадки нескольких
(хотя бы трёх) участников за круглым столом, при которой любые два соседа дружат,
участников из каждого региона за столом окажется не более половины общего числа де-
тей за столом. Докажите, что участников можно рассадить по n кабинетам так, чтобы
любые два друга оказались в разных кабинетах.
Решение. Рассмотрим граф G, в котором вершины соответствуют участникам, а рёбра
соединяют пары друзей. Тогда нам известно, что вершины можно окрасить в n цветов так,
что в каждом простом цикле не более половины вершин будут одноцветными (назовём
такую окраску приятной). Нужно же доказать, что можно вершины окрасить в n цветов
правильным образом.

LII Всероссийская математическая олимпиада школьников

Назовём цвет правильным, если никакие две вершины этого цвета не соединены; иначе
назовём его неправильным. Рассмотрим любую приятную окраску вершин и два цвета A
и B в ней. Мы докажем, что можно перекрасить вершины этих цветов (окрасив каждую
снова либо в A, либо в B) так, что оба этих цвета станут правильными, и раскраска оста-
нется приятной. Заметим, что при такой операции любой другой правильный цвет оста-
нется правильным. Значит, проделав такую операцию несколько раз, задействовав каж-
дый цвет хотя бы по разу, мы получим правильную окраску вершин, что и требовалось.

Осталось показать, как совершить перекраску для двух цветов. Рассмотрим лишь
граф H на вершинах цветов A и B (со всеми рёбрами, соединяющими пары этих вер-
шин). Если в H есть простой цикл, то в нём не больше половины вершин цвета A и не
больше половины — цвета B, то есть вершин обоих цветов в нём ровно по половине. Сле-
довательно, этот цикл чётный. Таким образом, в графе H нет нечётных циклов; как из-
вестно, вершины такого графа можно правильно окрасить в два цвета.
Сделаем такую окраску в цвета A и B; оба этих цвета стали правильными. Осталось
доказать, что в любом простом цикле в исходном графе G по-прежнему не более половины
вершин одного цвета. Это условие могло нарушиться лишь для цветов A или B; покажем,

что оно не нарушилось, скажем, для цвета A. Сопоставим каждой вершине цикла, име-
ющей цвет A, следующую за ней по циклу. Сопоставленные вершины будут иметь цвета,
отличные от A, и все они будут различными. Значит, вершин цвета A в цикле столько же,
сколько сопоставленных им вершин других цветов, то есть не больше половины общего
числа вершин в цикле, что и требовалось.
Замечание. Рассуждение из последнего абзаца решения показывает, что если верши-
ны окрашены правильным образом, то в любом простом цикле не более половины одно-
цветных вершин. Таким образом, существование правильной раскраски равносильно су-
ществованию раскраски из условия.

Заключительный этап, 2025–2026 учебный год

Ответ: На олимпиаду приехало несколько участников из n > 1 регионов, некоторые из них дру-