|
|
 |
Условие
За каждым из двух круглых столиков сидит по $n$ гномов. Каждый дружит только со своими соседями по столику слева и справа. Добрый волшебник хочет рассадить гномов за один круглый стол так, чтобы каждые два соседних гнома дружили между собой. Он имеет возможность подружить $2n$ пар гномов (гномы в паре могут быть как с одного столика, так и с разных), но после этого злой волшебник поссорит между собой $n$ пар гномов из этих $2n$ пар. При каких $n$ добрый волшебник может добиться желаемого, как бы ни действовал злой волшебник?Решение
Обозначим через $A_1, A_2, \ldots, A_n$ гномов, сидящих за первым столиком, а через $B_1, B_2, \ldots, B_{n}$ — гномов, сидящих за вторым столиком.
Случай нечётного $n$. Пусть $n=2k-1$. Стратегия за доброго волшебника: подружить пары гномов $(A_i, B_i)$ и $(A_i, B_{i+1})$ (здесь мы считаем, что $B_{2k}=B_1$). Очевидно, что добрый волшебник подружил ровно $2n$ пар гномов. Проверим, что при такой стратегии злой волшебник не сможет помешать доброму.
Действительно, так как злой волшебник ссорит ровно половину всех дружб, то либо среди пар $(A_i, B_i)$ хотя бы $k$ всё ещё дружат, либо среди пар $(A_i, B_{i+1})$ хотя бы $k$ все еще дружат. Тогда в первом случае найдется $i$, для которого обе пары гномов $(A_i, B_i)$, $(A_{i+1}, B_{i+1})$ дружат, и добрый волшебник может рассадить их за стол следующим образом: $A_{i}, B_i, B_{i-1}, \ldots, B_{i+1}, A_{i+1}, A_{i+2}, \ldots, A_{i-1}$. Второй случай аналогичен.
Случай чётного $n$. Приведем стратегию злого волшебника. Пусть добрый волшебник уже как-то подружил $2n$ пар гномов; построим граф, в котором вершины соответствуют гномам, а ребра — парам гномов, которые подружил добрый волшебник. Покрасим гномов за первым столиком в белый и чёрный цвета в шахматном порядке, а за вторым — в красный и синий. Так как сумма степеней всех вершин равна $4n$, найдётся цвет, для которого сумма степеней вершин, покрашенных в этот цвет, не превосходит $n$. Не умаляя общности, это белый цвет, то есть гномы $A_1, A_3, \ldots, A_{n-1}$. Пусть злой волшебник поссорит все пары друзей, в которые входят гномы белого цвета. Тогда единственные оставшиеся друзья любого белого гнома $A_{2l+1}$ — его старые соседи $A_{2l}$ и $A_{2l+2}$, и очевидно, что добрый волшебник не сможет рассадить всех гномов за один стол требуемым образом.
