Известно, что некоторые сенаторы между собой в ссоре. Проверено, однако, что как бы мы не посадили их всех или любую группу (3 или более) из них по кругу, найдется пара соседей не в ссоре. Весь сенат усадили за круглый стол. Если два соседа не в ссоре, они могут поменяться местами. Докажите, что сенаторы могут расположиться в любом круговом порядке (порядки, полученные поворотом, не различаются).
Подсказка
Попробуйте доказать индукцией по количеству сенаторов.
Решение
Докажем индукцией по числу сенаторов. База. Для трех сенаторов есть только два круговых порядка. Они получаются друг из друга пересадкой двух соседей, которые не в ссоре. Шаг индукции. Найдется сенатор А, который в ссоре не более чем с одним сенатором (иначе часть сенаторов можно будет рассадить по кругу так, что у каждого соседями будут враги). Пусть Б в ссоре с А (а если А дружит со всеми, то Б — любой другой). По предположению индукции, если А уйдет из-за стола, то есть способ рассадить оставшихся в нужном круговом порядке. Однако это можно сделать и при наличии А. Придвинем А к Б (это можно сделать) и попросим А и Б взяться за руки. Считая эту пару сенатором Б, рассадим всех в нужном порядке вышеуказанным способом. Теперь можно А посадить на нужное место, последовательно «отодвигая» его от Б.