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