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

[Mathusic]

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

Я имела в виду последовательности для тех $n$, для которых существуют последовательности обоих видов: приводящие и не приводящие к тождественной перестановке. Когда последовательность одного вида не существует, сравнивать нечего, вопрос становится бессмысленным.

При $n=4$ две максимальные посл-ти приводят к тождественной перестановке $\mathrm{id}$. Проверил вручную!

[Nataly-Mak]

Mathusic в сообщении #384150 писал(а):

При $n=4$ две максимальные посл-ти приводят к тождественной перестановке $\mathrm{id}$. Проверил вручную!

И что из этого?
Для $n=15$ шесть максимальных последовательностей приводят к тождественной перестановке.
Проверила на машине

[Nataly-Mak]

На конкурсе неполадки.
Как я поняла, всем участникам надо снова ввести свои результаты.

Пока ещё не все проснулись, моя команда побывала на 4-ом месте

Rank  Score  Contestant  Last Improvement 

1 24.73 Jarek Wroblewski Wroclaw, Poland 6 Dec 2010 06:20
2 22.83 Giuliano Bertoletti Parma, Italy 6 Dec 2010 01:34
3 21.94 Yirmy Yasovsky Rehovot, Israel 6 Dec 2010 06:58
4 21.37 Natalia Makarova Saratov, Russia 6 Dec 2010 07:10
5 20.77 Byron Knoll Vancouver, British Columbia, Canada 6 Dec 2010 03:58
6 19.61 Sebastian Luther Magdeburg, Germany 6 Dec 2010 06:49
7 17.68 Kendrick Boyd Madison, Wisconsin, United States 6 Dec 2010 05:42
8 17.11 Osama Elahmy Adly Cairo, Egypt 6 Dec 2010 07:03

[Mathusic]

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

И что из этого?

При $n=4$ все максимальные последовательности приходят только к $\mathrm{id}$. Вы же сами спрашивали.

[dvorkin_sacha]

Максимальная последовательность для порождения тождественной перестановки ($n=20$, расчет точный и занимающий всего пару минут) следующая:

$9, 16, 5 , 15, 8 ,14 ,1 ,10, 4 ,13 ,20, 18, 19, 11, 17, 2, 3, 12, 6, 7$

Число перекладываний - 224.

[Mathusic]

Вот, кстати, интересно.
Пусть $\varphi: S_n \to \mathbb{N}\cup\{0\}$ - функция количества перекладываний.
Тогда как будет выглядеть $\displaystyle M(n)=\sum_{\sigma \in S_n}{\varphi(\sigma)}$ ? И как ведёт себя на бесконечности $\frac{M(n)}{n!}$ ? (вероятно, уходит на беск-ть)

[Nataly-Mak]

А это последовательность для $n=20$ (насчёт максимальности ничего не могу сказать; скорее всего, не максимальная), не приводящая к тождественной перестановке:

232: 2 3 4 5 8 1 20 17 6 14 18 13 7 19 11 12 10 9 16 15 -> 
1 18 17 16 15 14 8 7 2 3 4 5 6 9 10 11 12 13 19 20

Получена по программе Кнута.

И опять же: последовательность, не приводящая к тождественной перестановке, даёт больше шагов, чем приводящая (если правильно, что максимальная последовательность для $n=20$, приводящая к тождественной перестановке, даёт 224 шага).

[Nataly-Mak]

Это для $n=12$, первая последовательность приводит к тождественной перестановке (63 шага), а вторая не приводит (65 шагов):

10 11 7 1 3 8 2 9 12 6 4 5
2 6 1 10 11 8 12 3 4 7 9 5

Оба результата максимальные.

-- Вт дек 07, 2010 09:50:45 --

А вот для $n=15$ непонятно.

В последовательности A000376 приведён результат 112 шагов.
Это для последовательности, которая приводит к тождественной перестановке.
Но вот передо мной 6 последовательностей, все приводят к тождественной перестановке и дают один и тот же результат - 113 шагов.

В последовательности A000375 указан результат 113 шагов.
Это последовательность, которая не приводит к тождественной перестановке. Какая она, кстати?

Нет ли здесь ошибки в последовательности A000376?

[dvorkin_sacha]

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

А вот для $n=15$ непонятно.

В последовательности A000376 приведён результат 112 шагов.
Это для последовательности, которая приводит к тождественной перестановке.
Но вот передо мной 6 последовательностей, все приводят к тождественной перестановке и дают один и тот же результат - 113 шагов.

На нобеля замахнулись?

[Nataly-Mak]

Решила проверить ещё раз 6 последовательностей для $n=15$.
Оказалось, что я просто не разглядела итоговую последовательность; для всех 6 последовательностей она одинаковая и очень близка к тождественной, всего два числа переставлены:

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

Так что всё правильно в OEIS.

[Nataly-Mak]

Это последовательность для $n=15$, приводящая к тождественной перестановке, 112 шагов (максимум):

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

Найдена по программе svb.

[dvorkin_sacha]

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

Это последовательность для $n=15$, приводящая к тождественной перестановке, 112 шагов (максимум):

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

Найдена по программе svb.

Вот еще одна последовательность для $n=15$ со 112 шагами:
$3,10,4,2,7,14,15,11,1,9,5,13,6,8,12$
Этими двумя все и исчерпывается (найдены за неуловимые доли секунды).

-- Вт дек 07, 2010 15:31:01 --

dvorkin_sacha в сообщении #384393 писал(а):

Максимальная последовательность для порождения тождественной перестановки ($n=20$, расчет точный и занимающий всего пару минут) следующая:

$9, 16, 5 , 15, 8 ,14 ,1 ,10, 4 ,13 ,20, 18, 19, 11, 17, 2, 3, 12, 6, 7$

Число перекладываний - 224.

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

[Pavlovsky]

Mathusic в сообщении #384458 писал(а):

Вот, кстати, интересно.
Пусть $\varphi: S_n \to \mathbb{N}\cup\{0\}$ - функция количества перекладываний.
Тогда как будет выглядеть $\displaystyle M(n)=\sum_{\sigma \in S_n}{\varphi(\sigma)}$ ? И как ведёт себя на бесконечности $\frac{M(n)}{n!}$ ? (вероятно, уходит на беск-ть)

Совсем не факт, что бесконечность. Для $(n-1)!$ перестановок $\varphi(\sigma)=1$

PS Немного не понятно, как все это может помочь в поисе перестановок с максимальным количеством перекладываний?!

[Mathusic]

Pavlovsky в сообщении #384656 писал(а):

Совсем не факт, что бесконечность. Для $(n-1)!$ перестановок $\varphi(\sigma)=1$!

Естественно: пока не доказано - не факт. Более того, для $(n-1)!$ перестановок $\varphi(\sigma)$ и вовсе $0$

Pavlovsky в сообщении #384656 писал(а):

PS Немного не понятно, как все это может помочь в поисе перестановок с максимальным количеством перекладываний?!

Ну и не обязательно должно быть, хотя, возможно, помочь и может.

[Pavlovsky]

Pavlovsky в сообщении #375881 писал(а):

Свойство №2 В перестановке с максимальным количеством ходов, ни одна карта не должна стоять на своей позиции. То есть не должно быть, чтобы карта с номером i стояла на позиции i.

Родилась такая вот задачка. Дано натуральное число N. Сколько перестановок из чисел от 1 до N удовлетворяют этому свойству?