Олимпиадная задача: рыцари и перестановки за круглым столом с Мерлином (8-10 класс)
Задача
За круглым столом заседают 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-й день. Пусть для произвольного порядка Мерлин выполнит такой обход: двигаясь всё время по часовой стрелке, пройдёт от 1-го до 2-го, затем до 3-го, до 4-го, ..., доN-го и снова до 1-го. Свяжем с порядкомчисло оборотовМерлина вокруг стола. Легко убедиться, что при разрешённой пересадке двух рыцарей число оборотов не меняется. Однако числа оборотов избранных порядков различны (дляk-го порядка число оборотов равноk), поэтому избранные порядки с разнымиkпересадками друг из друга не получаются. Рассаживая рыцарей в очередном избранном порядке, Мерлин может получить первое повторение не ранееN-го дня.
Ответ
N дней.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь