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

[Nataly-Mak]

(Оффтоп)

Не надо бить диски, бейте мозги!

[Pavlovsky]

Свойство №1 Пусть у нас есть некоторая перестановка P, которая за m ходов приводит к 1 впереди. Если на позиции i стоит карта с номером i, то инверитровав первые i карт мы получим перестановку, в которой 1 впереди становится за m+1 ходов.

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

Свойство №3 Пусть у нас есть некоторая перестановка P из n чисел, которая за m ходов приводит к 1 впереди. Тогда инвертировав эту перестановку и добавив с переди число n+1. Мы получим перестановку из n+1 числа с количеством ходов m+1. Если при этой операции у нас некатарая карта оказалась на своем месте, то можем воспользоваться свойством №1.
Пример.
Берем (2,3,1) инверитруем и добавляем вперед 4. Получилось (4,1,3,2). Число 3 оказалось на месте, преобразуем. Результат (3,1,4,2), количество ходов 4. Пользуясь этим свойством можно построить перестановку для любого n, пусть не максимальную но очень приличную.

[Nataly-Mak]

А можно как-нибудь теоретически вычислить максимальное число перекладываний для каждого $n$?
Это интересно знать, чтобы иметь определённую цель.
Я при вводе решений пытаюсь определить максимумы по системе баллов, но могу ошибиться.

Так, например, по моим расчётам такие максимумы:

n=19   218
n=23   350
n=29   669
n=31   728

У кого есть более точные значения?

[Nataly-Mak]

Ещё два предположительных максимума:

n=37   1063
n=41   1218

Вроде все максимумы идут в строгом порядке возрастания.

Предварительно удаётся найти примерно 0,3 от максимума. Это получается легко, по крайней мере, для перечисленных $n$.
А вот дальше уже сложнее

[maxal]

maxal в сообщении #375297 писал(а):

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

Раз никто не хочет доказывать, придётся самому.

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

[Nataly-Mak]

Похоже, максимумы на конкурсе меняются.

На второй или третий день соревнованмя у лидера было 24,54 балла.
Потом через день или два вдруг стало 24,4 балла, потом 24,44.

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

Нечто подобное я наблюдала и в прошлом конкурсе.

-- Чт ноя 18, 2010 03:48:33 --

Да, сомнений не осталось, максимумы меняются.

Сейчас заглянула в таблицу результатов.
Вчера у меня было 13,83 балла, а сегодня 13,66. Тоже произошло уменьшение. По той же самой причине.
Уменьшение произошло у всех участников, кто ужё ввёл результат для тех $n$, для которых изменился максимум.

[Pavlovsky]

А почему в конкурсе принимают цчастие только простые числа? Это не спроста. Значит для составных чисел существуют процедуры декомпозиции?!

[Jarek]

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

А почему в конкурсе принимают цчастие только простые числа? Это не спроста. Значит для составных чисел существуют процедуры декомпозиции?!

Sorry for responding in English, but I do not have a keyboard with Russian letters.

In my opinion primality is irrelevant for the contest problem. Al Zimmermann's contests have 25 subproblems and most likely Al wanted the highest N to be around 100 for the contest to be interesting. I guess he just wanted to select somehow 25 numbers out of the first 100 - taking primes is just one of the ways to do this.

[Nataly-Mak]

Jarek
А вы участвуете в конкурсе?

Что вы думаете по поводу изменения максимальных результатов? Как выявить эти изменения?
Например, примерный максимальный результат для $n=97$ 10629, но он будет изменяться несколько раз в ходе конкурса, конечно, в сторону увеличения.

[Jarek]

Yes, I do participate (currently I am 11th with 18.03).

It is natural that the best known results are being frequently improved, especially at the early stage of the contest, so there is no surprise for me. As the contest progresses, changes can still happen, but should be rather smaller. It is normal that during first days after the contest problem is announced, changes are very large. In my opinion this particular contest problem (and the contest setup which includes large N) invites such large changes.

I think that the score drops should be smaller now, but from time to time our scores may slide down slowly (I just lost 0.05 last hour).

However we cannot rule out that one of the leaders suddenly works out a new clever method, which would produce large improvement of the best known results, even later in the contest.

[Nataly-Mak]

Да, я уже вижу вас в таблице конкурса.
У вас очень высокие результаты.

Приглашаю вас принять участие в проводимом мной конкурсе "Нетрадиционные пандиагональные квадраты":
topic38320.html

[dvorkin_sacha]

Jarek в сообщении #376911 писал(а):

However we cannot rule out that one of the leaders suddenly works out a new clever method, which would produce large improvement of the best known results, even later in the contest.

Согласен с Вами, что этого исключать нельзя. Более того, если появится (или появился) новый продвинутый алгоритм, то скорее всего его автор опубликует свои результаты в последний день конкурса, дабы оставить своих коллег по конкурсу не у дел.

[Nataly-Mak]

А откуда у автора "продвинутого алгоритма" уверенность в том, что другие коллеги по конкурсу не изобрели ещё более продвинутый алгоритм и опубликуют свои результаты а последнюю минуту?

В прошлом конкурсе борьба за первое место шла буквально до последней минуты, на последней минуте тот, кто был вторым, вырвал победу. Организатору конкурса пришлось ввести в учёт тысячные доли балла, чтобы определить победителя.

[dvorkin_sacha]

Каждый волен сам выбирать стратегию поведения: вот Вы, например, ни словом не обмолвились по поводу n = 17.

[12d3]

Nataly-Mak
А какие у вас текущие результаты, т.е. количество перекладываний для каждого $n$?