Card или Topswops

[square]

13 ноября у Зиммерманна стартовал новый конкурс - Card
//текст доступен после регистрации//

Нет ли здесь участников этого конкурса или просто интересующихся?
Хотелось бы обменяться мнениями об этих интересных задачках по перекладыванию карт.

Смысл задачи такой. Вот, например, последовательность из 16 карт:

Код:

9 12 6 7 2 14 8 1 11 13 5 4 15 16 10 3

Начинаем перекладывать карты. На верхней карте (первая слева) написано число 9, значит берём первые 9 карт сверху и кладём их в обратном порядке, остальные карты кладём так, как они лежали:

Код:

11 1 8 14 2 7 6 12 9 13 5 4 15 16 10 3

Это один шаг сделан. Теперь на верхней карте написано число 11, берём первые 11 карт сверху и кладём их в обратном порядке. И так далее. Когда на месте первой карты появится карта с числом 1, процесс завершён, больше перекладывать нечего. Считаем, сколько всего сделано шагов.
Задача в том, что надо найти такую исходную последовательность, для которой количество перекладываний (шагов) будет максимальным.
В приведённом примере количество шагов равно 139, это максимальное количество для n=16.

В конкурсе надо брать колоды состоящие из n=2, 3, 5, 7, ..., 97 (все простые числа) карт.

[Лев]

А цикл создать никак не получится?

[square]

Какой цикл?

Берём, например, колоду из 97 карт. Надо сложить эти карты в некоторой последовательности,так чтобы перкладываний получилось максимальное число.
Как их сложить? Как найти такую последовательность?
Понятно, что полный перебор всех комбинаций для больших чисел невозможен.
Говорят, что его удаётся сделать для n<17.

Кстати, для n=17 последовательность есть в OEIS, она приводит к максимальному количеству шагов - 159.
Так что, собственно, задачу надо начинать решать с n=19. Максимум для этого n, а также и для всех больших, неизвестен.

Я, например, получила для n=19 202 шага. Какой максимальный результат будет, не знаю.
А для n=97 получила 10668 шагов. Думаю, что это далеко не максимум.

[Илья]

Какой цикл?

Лев, наверное, имеет в виду, когда n=∞

[square]

Может быть, имеется в виду, что процесс перекладываний может зациклиться, то есть карта с числом 1 никогда не появится на первом месте?
Нет, такое зацикливание исключено. Доказано на форуме dxdy.ru.

Так что количество шагов (перекладываний) всегда конечно, для любой последовательности.

[Илья]

Доказано на форуме dxdy.ru

А можно ссылочку на доказательство?

[square]

Конечно, можно:
//текст доступен после регистрации//

В этой теме есть ещё много полезной информации.