Задание №176996: Турнир городов

4. [7] За каждым из двух круглых столиков сидит по n гномов. Каждый дружит только
со своими соседями по столику слева и справа. Добрый волшебник хочет рассадить гномов за
один круглый стол так, чтобы каждые два соседних гнома дружили между собой. Он имеет
возможность подружить 2n пар гномов (гномы в паре могут быть как с одного столика, так
и с разных), но после этого злой волшебник поссорит между собой n пар гномов из этих 2n
пар. При каких n добрый волшебник может добиться желаемого, как бы ни действовал злой
волшебник?
(Михаил Святловский)
Ответ: при всех нечётных n > 1.
Обозначим через A ,A ,...,A гномов, сидящих за первым столиком, а через B ,B ,...,B —
1 2 n 1 2 n
гномов, сидящих за вторым столиком.

Случай нечётного n. Пусть n = 2k 1. Стратегия доброго волшебника: подружить пары гномов
−
(A ,B ) и (A ,B ) (здесь мы считаем, что B = B ). Очевидно, что добрый волшебник подружил
i i i i+1 2k 1
ровно 2n пар гномов. Проверим, что при такой стратегии злой волшебник не сможет помешать
доброму.
Действительно, так как злой волшебник ссорит ровно
половину указанных пар, то либо среди пар (A ,B ) хо-
i i
тя бы k всё ещё дружат, либо среди пар (A ,B ) хотя бы k
i i+1
все еще дружат. Тогда в первом случае найдется i, для ко-
торого обе пары гномов (A ,B ), (A ,B ) дружат, и доб-
i i i+1 i+1
рый волшебник может рассадить их за стол следующим
образом: A ,B ,B ,...,B ,A ,A ,...,A . Второй
i i i−1 i+1 i+1 i+2 i−1
случай аналогичен.
Случай чётного n. Приведем стратегию злого волшебника. Пусть добрый волшебник уже как-
то подружил 2n пар гномов; построим граф, в котором вершины соответствуют гномам, а ребра
— парам гномов, которые подружил добрый волшебник. Покрасим гномов за первым столиком в
белый и чёрный цвета в шахматном порядке, а за вторым — в красный и синий. Так как сумма
степеней всех вершин равна 4n, найдётся цвет, для которого сумма степеней вершин, покрашенных
в этот цвет, не превосходит n. Не умаляя общности, это белый цвет, то есть гномы A ,A ,...,A .
1 3 n−1
Пусть злой волшебник поссорит все пары друзей, в которые входят гномы белого цвета. Тогда
единственные оставшиеся друзья любого белого гнома A — его старые соседи A и A ,
2l+1 2l 2l+2
и очевидно, что добрый волшебник не сможет рассадить всех гномов за один стол требуемым
образом.