2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 16  След.
 
 Re: Новый конкурс Зиммерманна
Сообщение16.11.2010, 11:58 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов

(Оффтоп)

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

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


21/02/10
1594
Екатеринбург
Свойство №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, пусть не максимальную но очень приличную.

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


22/03/08

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

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

Код:
n=19   218
n=23   350
n=29   669
n=31   728


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

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


22/03/08

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

Код:
n=37   1063
n=41   1218

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

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

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


11/01/06
5604
maxal в сообщении #375297 писал(а):
Предлагаю для начала доказать, что процесс переворачиваний не может зациклиться.

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

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

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


22/03/08

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

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

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

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

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

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

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

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


21/02/10
1594
Екатеринбург
А почему в конкурсе принимают цчастие только простые числа? Это не спроста. Значит для составных чисел существуют процедуры декомпозиции?!

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


18/11/10
75
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.

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


22/03/08

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

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

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


18/11/10
75
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.

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


22/03/08

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

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

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


04/11/10

141
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.

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

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


22/03/08

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

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

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


04/11/10

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

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


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

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

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



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

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


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

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