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