|
|
 |
Условие
За круглым столом заседают N рыцарей. Каждое утро чародей Мерлин
сажает их в другом порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь из предыдущих дней:
тогда заседания прекратятся. Какое наибольшее число дней Мерлин гарантированно может проводить заседания?
(Рассадки, получающиеся друг из друга поворотом, считаются одинаковыми. Мерлин за столом не сидит.)
Решение
Занумеруем в первый день сидящих рыцарей по часовой стрелке от 1 до N. Порядок за столом будем описывать строкой этих номеров, перечисляя рыцарей по часовой стрелке. Назовём избранными порядки вида k, k – 1, ..., 2, 1, k + 1, k + 2, ..., N для k = 1, 2, 3, ..., N – 1 (N-й избранный порядок совпадает с (N–1)-м, поэтому он не нужен). Докажем, что из любого порядка можно пересесть в избранный.
Для этого осуществим пересадку, при которой левая группа k, k – 1, ..., 2, 1 максимальная из возможных. Покажем, что остальные рыцари при этом автоматически сидят в
нужном порядке (k + 1, k + 2, ..., N). Пусть это не так. Будем двигать число
k + 1 по часовой стрелке. Если по пути k + 1 упрётся в k + 2, будем двигать эту пару. Упёршись парой в k + 3, будем двигать тройку и т. д. В итоге до k доедет поезд k + 1, k + 2, ..., k + m. При этом k + m < N (иначе никакого движения вообще не было). Прогоним все числа поезда, кроме k + 1, сквозь левую группу, а k + 1 присоединим к ней. Противоречие с максимальностью левой группы.
Ясно, что пересаживаясь каждый день в избранном порядке, рыцари повторятся не позднее чем на N-й день.
Ответ
N дней.
Замечания
12 баллов
