2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 16  След.
 
 Конкурс Зиммерманна о перекладывании карт
Сообщение14.11.2010, 13:07 
Заблокирован
Аватара пользователя


22/03/08

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

Перевела описание задачи с английского в Гугле, ну ничего не поняла.
Как надо карты перекладывать?
Вот пример там приведён, дана колода из 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) карт и делать с этими колодами то же самое. А что "то же самое"?

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 13:31 
Заслуженный участник


28/04/09
1933
Надо найти такую последовательность карт в колоде (заданной длины), для которой было бы максимально число перекладываний. Перекладывания организуются следующим образом:
    смотрим, какая верхняя карта у текущей последовательности,
    берем сверху число карт, равное числу, написанному на этой верхней карте,
    перетасовываем эти карты в обратном порядке,
    кладем их сверху колоды.
Очевидно, что если сверху оказывается карта с числом 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, как в примере) это правило почему-то выполняется (не знаю, как дальше).

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 13:36 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 14:22 
Заслуженный участник


28/04/09
1933
Интуиция подсказывает мне, что в конкурсах Зиммерманна обычно побеждают люди, имеющие доступ к кластеру и, в то же время, придумывающие весьма неслабые алгоритмы перебора (иногда под отдельные подзадачи различные).
Скажем, в этой задаче полный разумный перебор без аппаратных оптимизаций для $n=13$ длится на моем компьютере пару минут. Но уже для $n=17$ перебор слишком долог даже с учетом разного рода неалгоритмических оптимизаций. Т.е. нужно либо искать алгоритм с более жесткими (и в то же время правильными) условиями отброса некоторых последовательностей, либо алгоритм, дающей не самое оптимальное, но близкое к оптимальному решение (подозреваю, что в настоящее время все решения для больших $n$ именно таким образом и получены).
Nataly-Mak в сообщении #374959 писал(а):
А систему баллов вы поняли?
Система баллов такая же, как и в других его конкурсах. По каждой задаче ($n=2,3,5\dots$) выявляется участник, чье решение приводит к максимальному числу перекладываний. Его решение принимается за эталон, т.е. все участники, пославшие такое же решение или решение, приводящее к такому же количеству перекладываний, получают 1 балл за эту задачу; все остальные $\text{---}$ долю балла, равную отношению числа перекладываний, соответствующего их решению, к эталонному числу перекладываний.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 15:52 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 16:17 
Заслуженный участник


28/04/09
1933
Nataly-Mak в сообщении #375023 писал(а):
А сейчас я ручками посчитала для колоды из 5 карт. У меня получилось максимальное число перекладываний 7. А у вас сколько?
См. последовательность A000375 OEIS. Ее ближайшая родственница A000376 (если я правильно понял) дает количество перекладываний, приводящих к последовательности в естественном порядке (эта последовательность немного отличается от A000375, см. ниже).
EtCetera в сообщении #374955 писал(а):
правило почему-то выполняется
как выяснилось благодаря OEIS, правило не выполняется при $n=12,15,16,\dots$

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 16:21 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Итак, я стартовала :-)

Код:
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 балла, значит, мои решения совпали с максимальными. Правильно?

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 18:40 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение14.11.2010, 21:33 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение15.11.2010, 05:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вообще этот конкурс намного проще предыдущего.
Можно никакие программы не писать, а перекладывать вручную.
Берёте произвольную комбинацию из $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 балла.

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение15.11.2010, 06:11 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение15.11.2010, 06:25 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение15.11.2010, 09:17 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение15.11.2010, 21:43 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение16.11.2010, 10:43 


04/11/10

141

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 229 ]  На страницу 1, 2, 3, 4, 5 ... 16  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group