Форум умных людей

13 ноября у Зиммерманна стартовал новый конкурс - Card
http://www.azspcs.net/Contest/Cards

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

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

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

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

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

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

Какой цикл?

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

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

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

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

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

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

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

Конечно, можно:
http://dxdy.ru/topic38394-15.html

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