Круглый стол

У короля Артура за круглым столом сидит чётное число рыцарей. Когда за окном проходит королева Гвиневра, они все бросаются к окну, а потом снова рассаживаются, но в другом, случайном порядке. Доказать, что найдутся два рыцаря, расстояние между которыми не изменится.

Решение

Пусть все попарные расстояния между рыцарями после пересадки изменились, обозначим число рыцарей — $n$ . Будем считать, что каждый рыцарь не бросается к окну, а просто проходит вокруг стола против часовой стрелки и садится на $k_i$ кресло, считая от своего. Легко видеть, что все числа $k_i$ разные и принимают значения от $0$ до $n-1$ .

Попросим теперь рыцарей пересаживаться по одному. То есть, первый рыцарь встаёт и садится на $k_i$ кресло, считая от своего, выгоняя того, кто там сидел. Тот, в свою очередь идёт дальше и т.д. Этот процесс может кончиться только тогда, когда кто-нибудь сядет в пустое кресло первого, завершив цикл. Сумма всех $k_i$ в цикле будет делитьса на $n$ . Всё перемещение рыцарей сведётся к некоторому числу таких циклов и, значит, общая сумма всех $k_i$ должна делиться на $n$ . С другой стороны она равна $0 + 1 + 2 + ... + (n-1) = (n-1) * n / 2$ . Значит $(n-1) / 2$ — число целое, а $n$ — нечётное.