ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116045
Темы:    [ Процессы и операции ]
[ Принцип крайнего (прочее) ]
[ Инварианты ]
Сложность: 5
Классы: 8,9,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 дней.

Замечания

12 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
Задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .