За круглым столом заседают N рыцарей. Каждое утро чародей Мерлин сажает их в другом
порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько
угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они
не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь
из предыдущих дней: тогда заседания прекратятся. Какое наибольшее число дней
Мерлин гарантированно может проводить заседания? (Рассадки, получающиеся друг из друга
поворотом, считаются одинаковыми. Мерлин за столом не сидит.)

Здравствуйте, baily, Вы писали:

<>

Пока не придумал доказательств, ставлю эксперименты (брутфорсю).

Для N=5 рыцари во второй же день переберут все браслеты (11 из 12). На третий день браслетов не останется.
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два класса).
И т.д.

Очевидно и важно, что из любого начального браслета в классе "все браслеты одного дня" можно достичь любого другого, поскольку рыцарям не запрещено делать перестановки туда-обратно. То есть, это не цепочка, а просто связный неориентированных граф.

 N / браслеты / классы / размеры классов
 4          3        2   1, 2
 5         12        2   1, 11
 6         60        3   1, 26, 33
 7        360        3   1, 57, 302
 8       2520        4   1, 120, 1191, 1208
 9      20160        4   1, 247, 4293, 15619
10     181440        5   1, 502, 14608, 78095, 88234
11    1814400        5   1, 1013, 47840, 455192, 1310354

На 12 брутфорсилка сломалась — закончилась память (я не особо старался её оптимизировать).

Количество браслетов растёт, очевидно, по экспоненте, а количество классов — как-то очень полого (линейно?)

Здравствуйте, Кодт, Вы писали:

К>Пока не придумал доказательств, ставлю эксперименты (брутфорсю).

К>Для N=5 рыцари в первый же день переберут все браслеты (12 штук).
А почему 12? Ты зеркальные отображения считаешь одинаковыми?

Здравствуйте, _DAle_, Вы писали:

К>>Для N=5 рыцари в первый же день переберут все браслеты (12 штук).
_DA>А почему 12? Ты зеркальные отображения считаешь одинаковыми?

Ой, чёрт, невнимательно условие прочёл. Там не браслеты, а только ожерелья.
Сейчас пересчитаю

Здравствуйте, baily, Вы писали:

Обновлённые результаты забега

 N  ожерелья  классы   размеры классов
 4         6       3   1, 1, 4
 5        24       4   1, 1, 11, 11
 6       120       5   1, 1, 26, 26, 66
 7       720       6   1, 1, 57, 57, 302, 302
 8      5040       7   1, 1, 120, 120, 1191, 1191, 2416
 9     40320       8   1, 1, 247, 247, 4293, 4293, 15619, 15619
10    362880       9   1, 1, 502, 502, 14608, 14608, 88234, 88234, 156190
11   3628800      10   1, 1, 1013, 1013, 47840, 47840, 455192, 455192, 1310354, 1310354

Закрадывается подозрение, что ответ — N-1. Интересно, как это доказать?

А классы размером 1 — это расстановка первого дня и зеркальная ей расстановка (в которой, понятное дело, все рыцари являются соседями первого дня, и не могут сдвинуться с места).

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, baily, Вы писали:

К>Обновлённые результаты забега
К>

К> N  ожерелья  классы   размеры классов
К> 4         6       3   1, 1, 4
К> 5        24       4   1, 1, 11, 11
К> 6       120       5   1, 1, 26, 26, 66
К> 7       720       6   1, 1, 57, 57, 302, 302
К> 8      5040       7   1, 1, 120, 120, 1191, 1191, 2416
К> 9     40320       8   1, 1, 247, 247, 4293, 4293, 15619, 15619
К>10    362880       9   1, 1, 502, 502, 14608, 14608, 88234, 88234, 156190
К>11   3628800      10   1, 1, 1013, 1013, 47840, 47840, 455192, 455192, 1310354, 1310354
К>

К>Закрадывается подозрение, что ответ — N-1. Интересно, как это доказать?

Хм.. http://mathworld.wolfram.com/EulersNumberTriangle.html, http://en.wikipedia.org/wiki/Eulerian_number

Здравствуйте, _DAle_, Вы писали:

_DA>Хм.. http://mathworld.wolfram.com/EulersNumberTriangle.html, http://en.wikipedia.org/wiki/Eulerian_number

Что-то я не вкурил, как соотнести классы ожерелий и классы перестановкок с подъёмами.
Хотя... Наверное, можно показать, что пересаживание рыцарей не изменяет количество подъёмов. В этом случае неважно, чему равно 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>>Хм.. http://mathworld.wolfram.com/EulersNumberTriangle.html, http://en.wikipedia.org/wiki/Eulerian_number

К>Что-то в лоб не вышло.

Да, в лоб не получается, надо как-то преобразовывать задачу... Но я думаю, что можно попробовать забыть про это и построить конструктивное решение, переводя целый класс в какое-то каноническое состояние, вот только пока не могу придумать, как это сделать )

Здравствуйте, _DAle_, Вы писали:

В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 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 и осталось показать, что каждое значение является классом эквивалентности, т.е все расстановки с одинаковым числом витков
достижимы между собой.