|
|
 |
Условие
Некоторые участники олимпиады дружат, и дружба взаимна. Назовём группу участников кликой, если все они дружат между собой. Их число называется размером клики. Известно, что максимальный размер клики чётен. Докажите, что участников можно рассадить по двум аудиториям так, что максимальные размеры клик в обеих аудиториях совпадают.
Решение
Разведём людей по комнатам R1 и R2: поместим в R1 максимальную клику, в R2 – оставшихся людей. Начнём пересаживать людей из R1 в R2 по одному. При каждом перемещении клика в R1 уменьшается не более чем на 1, а в R2 – увеличивается не более чем на 1. Поэтому можно добиться того, что в комнате R2 будет максимальная клика размера P + 1, а в комнате R1 – клика A0 размера P.
Пусть A – перемещённые лица из R1 в R2, так что A0 ∪ A – первоначальная максимальная клика. Поскольку число |A0 ∪ A| чётно, |A| имеет ту же чётность, что P = |A0|. В частности, |A| ≠ P + 1, то есть A – не максимальная клика в R2.
Если существует максимальная клика C в R2, не содержащая A, то для некоторого a ∈ A его возврат не уменьшает максимальной клики, ибо не разрушает C. Тогда получается требуемое разбиение.
Предположим, что все максимальные клики в R2 содержат A. Следовательно, их можно обозначить A ∪ K1, ..., A ∪ Kn; при этом
Ki ≠ ∅ для любого i.
Начнём переселять людей из R2 в R1 так. Пусть x1 принадлежит K1. Тогда x1 не образует клику с A0 (иначе A0 ∪ A ∪ x1 – ещё большая, чем возможно, клика).
Если x1 принадлежит пересечению всех Ki, то переселим x1 в R1 и задача решена.
В противном случае x1 не принадлежит Kj при некотором j ≠ 1. Можно считать, что x1 не принадлежит K2. Тогда выберем x2 ∈ K2, который не дружит с x1 (иначе K2 ∪ A не максимальная клика в R2). Отправим x1 и x2 в R1. Если все максимальные клики в R2 разрушены, остановимся. Если нет, пусть A ∪ K3 незатронутая клика. Возьмём x3 ∈ K3, не дружащего с x2 и т.д.
Каждый раз максимальный размер клики в R1 либо остается равным P, либо увеличивается до P + 1. Если это происходит перед последним ходом (то есть перед тем как все максимальные клики в R2 разрушены), мы получили требуемое. Аналогично, если после последнего хода размер клики в R1 сохранил свой размер P.
Мы пришли к следующей ситуации: перед последним пересаживанием нет (P+1)-клики в R1, но в последний момент l она появляется.
Однако по построению соседие члены последовательности x1, ..., xl (в частности, xl и xl–1) не дружат между собой.
Тогда возврат xl–1 обратно в R2 восстанавливает (P+1)-клику в R2 и не разрушает (P+1)-клику в R1 (ибо xl и xl–1 не в одной клике).
