За круглым столом заседают N рыцарей. Каждое утро чародей Мерлин сажает их в другом
порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько
угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они
не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь
из предыдущих дней: тогда заседания прекратятся. Какое наибольшее число дней
Мерлин гарантированно может проводить заседания? (Рассадки, получающиеся друг из друга
поворотом, считаются одинаковыми. Мерлин за столом не сидит.)
Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
Для N=5 рыцари во второй же день переберут все браслеты (11 из 12). На третий день браслетов не останется.
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два класса).
И т.д.
Очевидно и важно, что из любого начального браслета в классе "все браслеты одного дня" можно достичь любого другого, поскольку рыцарям не запрещено делать перестановки туда-обратно. То есть, это не цепочка, а просто связный неориентированных граф.
Здравствуйте, Кодт, Вы писали:
К>Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
К>Для N=5 рыцари в первый же день переберут все браслеты (12 штук).
А почему 12? Ты зеркальные отображения считаешь одинаковыми?
Здравствуйте, _DAle_, Вы писали:
К>>Для N=5 рыцари в первый же день переберут все браслеты (12 штук). _DA>А почему 12? Ты зеркальные отображения считаешь одинаковыми?
Ой, чёрт, невнимательно условие прочёл. Там не браслеты, а только ожерелья.
Сейчас пересчитаю
Закрадывается подозрение, что ответ — N-1. Интересно, как это доказать?
А классы размером 1 — это расстановка первого дня и зеркальная ей расстановка (в которой, понятное дело, все рыцари являются соседями первого дня, и не могут сдвинуться с места).
Что-то я не вкурил, как соотнести классы ожерелий и классы перестановкок с подъёмами.
Хотя... Наверное, можно показать, что пересаживание рыцарей не изменяет количество подъёмов. В этом случае неважно, чему равно E(n-1,k), — важно, что таких классов n-1.
Поскольку ожерелья не учитывают вращение, можем просто закрепить первого рыцаря на первой позиции. (Отсюда, кстати, следует n-1).
(1...,a,x,y,b,...z) выполняем пересаживание x,y (допустим, они не смежные)
(1...,a,y,x,b,...z)
где x,y — не смежные числа
a < x < y < b --- три подъёма
a < y > x < b --- два подъёма
То есть, класс наших ожерелий не совпадает с классом перестановок с одинаковыми подъёмами.
Что-то в лоб не вышло.
Да, в лоб не получается, надо как-то преобразовывать задачу... Но я думаю, что можно попробовать забыть про это и построить конструктивное решение, переводя целый класс в какое-то каноническое состояние, вот только пока не могу придумать, как это сделать )
В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому.
То есть: 1 2 3 4 5 — 1 виток 1 3 5 2 4 — 3 витка 1 5 4 3 2 — 4 витка
Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, _DAle_, Вы писали:
_DA>В общем, я понял, за что можно зацепиться.. _DA>Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому. _DA>То есть: _DA>1 2 3 4 5 — 1 виток _DA>1 3 5 2 4 — 3 витка _DA>1 5 4 3 2 — 4 витка
_DA>Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.
Не очень понял по поводу витков.. Можно поподробнее, что это такое?
Здравствуйте, baily, Вы писали:
B>Не очень понял по поводу витков.. Можно поподробнее, что это такое?
Пронумерум рыцарей при первой конфигурации. Круглый стол. Произвольная перестановка. Двигаемся только по часовой стрелке. Двигаемся от рыцаря с номером 1 до рыцаря с номером 2, потом от рыцаря с номером 2 к рыцарю с номером 3, и т.д. от рыцаря с номером N к рыцарю с номером 1. Количество витков — это количество раз, которое мы обошли стол.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, baily, Вы писали:
B>>Не очень понял по поводу витков.. Можно поподробнее, что это такое?
_DA>Пронумерум рыцарей при первой конфигурации. Круглый стол. Произвольная перестановка. Двигаемся только по часовой стрелке. Двигаемся от рыцаря с номером 1 до рыцаря с номером 2, потом от рыцаря с номером 2 к рыцарю с номером 3, и т.д. от рыцаря с номером N к рыцарю с номером 1. Количество витков — это количество раз, которое мы обошли стол.
Ясно. Я, когда решал, использовал аналогичный параметр. Рассматривал для каждого рыцаря расстояние против часовой стрелке до правого соседа в первоначальной расстановке.
И брал сумму таких расстояний по всем рыцарям. Похоже, что это в точности соответствует вашему определению витков. Только мое число будет ровно в N раз больше.
Инвариант найден верно. Как вы верно заметили, различных значений числа витков будет N-1 и осталось показать, что каждое значение является классом эквивалентности, т.е все расстановки с одинаковым числом витков
достижимы между собой.