Конкурс Зиммерманна о перекладывании карт

[Nataly-Mak]

У Зиммерманна стартовал новый конкурс.

Перевела описание задачи с английского в Гугле, ну ничего не поняла.
Как надо карты перекладывать?
Вот пример там приведён, дана колода из 6 карт.
Организуют её следующим образом (верхняя карта первая, она определяет какое-то количество, то есть количество "3", а количество чего? по сколько карт перекладывать?):

3, 6, 5, 1, 4, 2

Далее начинают перекладывать:

5,6,3,1,4,2
4,1,3,6,5,2
6,3,1,4,5,2
2,5,4,1,3,6
5,2,4,1,3,6
3,1,4,2,5,6
4,1,3,2,5,6
2,3,1,4,5,6
3,2,1,4,5,6
1,2,3,4,5,6

Сделали 10 перекладываний, получили карты в естественном порядке. Так надо, чтобы все карты в конце легли в естественном порядке?
По какому принципу надо перекладывать? Кто-нибудь понял? Объясните, пожалуйста.
Просто любопытно

Надо брать колоды из 2, 3, 5, 7, ..., 97 (простые числа до 100) карт и делать с этими колодами то же самое. А что "то же самое"?

[EtCetera]

Надо найти такую последовательность карт в колоде (заданной длины), для которой было бы максимально число перекладываний. Перекладывания организуются следующим образом:

смотрим, какая верхняя карта у текущей последовательности,
берем сверху число карт, равное числу, написанному на этой верхней карте,
перетасовываем эти карты в обратном порядке,
кладем их сверху колоды.

Очевидно, что если сверху оказывается карта с числом 1, процесс заканчивается (колода больше не меняется).
В данном примере:
$\underbrace{5\ 6\ 3\ 1\ 4}_5\ 2\Rightarrow\underbrace{4\ 1\ 3\ 6\ 5}_5\ 2$ и т.д.
Самое забавное, что процесс вовсе не обязан заканчиваться на последовательности в естественном порядке (главное, чтобы сверху появлялась 1), но для колод длиной 2, 3, 5, 7, 11 и 13 (и 6, как в примере) это правило почему-то выполняется (не знаю, как дальше).

[Nataly-Mak]

О, спасибо, вот как всё просто.
Теперь поняла.
Так вы уже нашли организацию колод до 13?

Вы будете участвовать в конкурсе?
Может быть, команду организуем?

В предыдущем конкурсе по магическим квадратам мы участвовали командой.

А систему баллов вы поняли? Я это даже не переводила.

[EtCetera]

Интуиция подсказывает мне, что в конкурсах Зиммерманна обычно побеждают люди, имеющие доступ к кластеру и, в то же время, придумывающие весьма неслабые алгоритмы перебора (иногда под отдельные подзадачи различные).
Скажем, в этой задаче полный разумный перебор без аппаратных оптимизаций для $n=13$ длится на моем компьютере пару минут. Но уже для $n=17$ перебор слишком долог даже с учетом разного рода неалгоритмических оптимизаций. Т.е. нужно либо искать алгоритм с более жесткими (и в то же время правильными) условиями отброса некоторых последовательностей, либо алгоритм, дающей не самое оптимальное, но близкое к оптимальному решение (подозреваю, что в настоящее время все решения для больших $n$ именно таким образом и получены).

Nataly-Mak в сообщении #374959 писал(а):

А систему баллов вы поняли?

Система баллов такая же, как и в других его конкурсах. По каждой задаче ($n=2,3,5\dots$) выявляется участник, чье решение приводит к максимальному числу перекладываний. Его решение принимается за эталон, т.е. все участники, пославшие такое же решение или решение, приводящее к такому же количеству перекладываний, получают 1 балл за эту задачу; все остальные $\text{---}$ долю балла, равную отношению числа перекладываний, соответствующего их решению, к эталонному числу перекладываний.

[Nataly-Mak]

Ну, мы в предыдущем конкурсе начали очень поздно и силы у нас были маленькие, в общем, всего три человека работали. Тем не менее, нам удалось занять 18-ое место. Это очень неплохо.
А об адреналине от участия я уж не говорю

Я сначала вообще без программ, ручками считала ёмкости своих магических квадратов. А потом участник команды svb сделал программу обсчёта квадратов, тут уже мне легче стало. А потом третий участник команды Pavlovsky разработал алгоритмы составления квадратов с заранее заданными водоёмами. Тут мы вообще стали очень быстро подниматься по турнирной таблице.

А сейчас я ручками посчитала для колоды из 5 карт. У меня получилось максимальное число перекладываний 7. А у вас сколько?

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

Ну, вот для колод из 2, 3, 5 карт у меня готовы решения, можно регистрироваться и начинать ввод решений

Да, так что, товарищи, организуем команду?

25 колод, если учесть что первые 5 колод достаточно просто решаются, остаётся 20 колод. Если раздать каждому участнику по две-три колоды, то ведь легко будет решить всего две задачки вместо 25.

[EtCetera]

Nataly-Mak в сообщении #375023 писал(а):

А сейчас я ручками посчитала для колоды из 5 карт. У меня получилось максимальное число перекладываний 7. А у вас сколько?

См. последовательность A000375 OEIS. Ее ближайшая родственница A000376 (если я правильно понял) дает количество перекладываний, приводящих к последовательности в естественном порядке (эта последовательность немного отличается от A000375, см. ниже).

EtCetera в сообщении #374955 писал(а):

правило почему-то выполняется

как выяснилось благодаря OEIS, правило не выполняется при $n=12,15,16,\dots$

[Nataly-Mak]

Итак, я стартовала

80 3.54 Ivan Kazmenko Saint-Petersburg, Russia 13 Nov 2010 19:29
81 3.38 Sebiha Sahin Mainz, Germany 13 Nov 2010 21:52
82 3.00 Natalia Makarova Saratov, Russia 14 Nov 2010 13:15
83 2.86 Torsten Faust Odense, Denmark 13 Nov 2010 18:11
84 2.71 M. Gokhan Habiboglu Istanbul, Turkey 13 Nov 2010 16:57
85 2.57 Gene Wagenbreth Topanga, California, United States 13 Nov 2010 21:36
86 2.57 John Gustaf Stebbins Shoreline, Washington, United States 14 Nov 2010 00:08
87 2.57 Tristrom Cooke

Оказывается, у меня и аккаунт сохранился от предыдущего конкурса.
Сразу вошла и ввела решения для 3 первых колод, получила 3 балла, значит, мои решения совпали с максимальными. Правильно?

Подключайтесь! Вместе будет веселей

[Nataly-Mak]

Сейчас вручную сделала для колоды из 7 карт 10 перекладываний с ходу, а должно быть 16.
За 10 перекладываний получила 0,68 балла.
Надо писать программу.
В OEIS вроде программа предлагается, но там, наверное, сложно разобраться, я не смотрела.

[Nataly-Mak]

Программку сочинила для колоды из 7 карт. По программе быстренько нашла вариант из 16 перекладываний.
Следующая колода у меня из 11 карт.

Ну, никто не хочет командную игру

[Nataly-Mak]

Вообще этот конкурс намного проще предыдущего.
Можно никакие программы не писать, а перекладывать вручную.
Берёте произвольную комбинацию из $n$ карт и начинаете перекладывать.
Получив количество перекладываний больше предыдущего, отправляете решение. Для одного $n$ можно отправить несколько решений.

Как я уже сообщала, для $n=7$ с ходу нашла решение вручную с 10 перекладываниями.
Конечно, максимальное количество перекладываний вручную получить невозможно для больших $n$. Но максимум и по программе сложно получить.

Написала вчера программу для $n=11$, пока нашла по этой программе только 30 перекладываний, а должно быть 51.

О системе баллов. Да, всё верно. За найденное решение дают долю от одного балла, соответствующую доле найденного количества перекладываний от максимального количества.
Так, например, за 30 перекладываний для $n=11$ мне дали 0,59 балла.

51 перекладывание - 1 балл
30 перекладываний - 0,59 балла

Ещё раз о командном участии.
Если кто-то хочет войти в команду, поясняю. Участие в команде вас абсолютно ни к чему не обязывает. Вы решаете задачи по мере возможности и присылаете мне свои решения. Вот и всё!
Я отправляю ваши решения по своему аккаунту, если они лучше уже полученных другими участниками команды решений. При этом, разумеется, участники команды не должны принимать индивидуального участия в конкурсе.

На сегодня у меня 5,59 баллов, 5 задач решила по максимуму и одну только на 0,59 балла.

Пишите мне в личку.

[maxal]

Предлагаю для начала доказать, что процесс переворачиваний не может зациклиться.

[Nataly-Mak]

Ну, наверное, Зиммерманн это доказал

[Nataly-Mak]

Найти максимумы сложно, найти наибольшее приближение к максимуму можно.
Так, я уже нашла для $n=11$ 47 перекладываний (максимум 51), для $n=13$ - 63 перекладывания (максимум 80).

[Nataly-Mak]

Может быть, здесь есть участники конкурса?
Я смотрю, в таблице довольно много участников из России. Один из них уже в десятке лучших.
Если кто знает, поделитесь, пожалуйста, информацией о максимумах для всех задач, чтобы знать, к какому результату стремиться.

Для $n = 2, 3, 5, 7, 11, 13, 17$ максимумы известны.
Для $n = 19$ по моим расчётам максимум равен 218, для $n = 23$ - 350. Но я могла ошибиться.
А что для следующих $n$?
Я дальше ещё не считала и ничего не вводила.

[dvorkin_sacha]

(Оффтоп)

Жалко бить диски из-за бутылки Клейна, если у тебя даже 16 гигов оперативки и RAID из 4-х дисков по 1 терабайту.