2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 25  След.
 
 Al Zimmerman - Delacorte Numbers
Сообщение06.10.2014, 09:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Стартовал новый конкурс Al Zimmerman - Delacorte Numbers. http://www.azspcs.net/Contest/DelacorteNumbers

Всех приглашаю участвовать и обсуждать тут. Поначалу задача совсем не интересная, но если присмотреться можно увидеть много интересных закономерностей. Пока что я нашел оптимальные (на данный момент) для первых 9 N. А вот на N=12 застрял и никак не могу найти оптимальное. Мне не очень нравится система оценок. Достаточно легко получить 0.99 для любого N, а вот 1.00 получить намного сложнее.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение06.10.2014, 12:27 
Аватара пользователя


21/02/10
1594
Екатеринбург
Ссылки на статьи по теме есть?

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение06.10.2014, 12:52 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #915688 писал(а):
Ссылки на статьи по теме есть?


Задача новая, ее придумал один из участников. Статей никаких нет.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение07.10.2014, 14:53 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Интересная аксиома для максимальных решений. Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата. Причем не важно в каком порядке. Это потому что эти числа имеют gcd=1 со всеми другими числами в квадрате.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение07.10.2014, 23:09 
Аватара пользователя


25/08/12
171
Germany
dimkadimon в сообщении #915649 писал(а):
А вот на N=12 застрял и никак не могу найти оптимальное.


It is not necessarily the case that you stuck with N=12. If your score seems to increase by 1.00 for N=3 to 11 it may only increase by 0.998 or similar. And such small differences will sum up so that suddenly your score drops by 0.01.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 01:32 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #916350 писал(а):
dimkadimon в сообщении #915649 писал(а):
А вот на N=12 застрял и никак не могу найти оптимальное.


It is not necessarily the case that you stuck with N=12. If your score seems to increase by 1.00 for N=3 to 11 it may only increase by 0.998 or similar. And such small differences will sum up so that suddenly your score drops by 0.01.


That's true. I think while I was improving my N=12, lower N got improved and I don't know which ones. This means that I will not know if I do find the optimal for N=12, because my score will still end in .99.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 06:27 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #916120 писал(а):
Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.


Совсем не обязательно в середину квадрата. Простые числа больше floor(N*N/2) и число 1 можно вообще не использовать при заполнении квадрата. А после заполнения квадрата другими числами, заполнить ими свободные места, порядок при этом не важен.

Это можно делать как для поиска минимума, так и для поиска максимума.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 11:01 
Заслуженный участник
Аватара пользователя


19/12/10
1546

(В порядке занудства)

dimkadimon в сообщении #916120 писал(а):
Интересная аксиома для максимальных решений. Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата. Причем не важно в каком порядке. Это потому что эти числа имеют gcd=1 со всеми другими числами в квадрате.
Скорее это лемма, чем аксиома.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 13:48 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #916496 писал(а):

(В порядке занудства)

dimkadimon в сообщении #916120 писал(а):
Интересная аксиома для максимальных решений. Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата. Причем не важно в каком порядке. Это потому что эти числа имеют gcd=1 со всеми другими числами в квадрате.
Скорее это лемма, чем аксиома.


Согласен, это больше похоже на лемму

-- 08.10.2014, 19:36 --

Pavlovsky в сообщении #916428 писал(а):
dimkadimon в сообщении #916120 писал(а):
Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.


Совсем не обязательно в середину квадрата. Простые числа больше floor(N*N/2) и число 1 можно вообще не использовать при заполнении квадрата. А после заполнения квадрата другими числами, заполнить ими свободные места, порядок при этом не важен.

Это можно делать как для поиска минимума, так и для поиска максимума.


Да действительно так. Это немного упрощает задачу.

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 15:22 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #916536 писал(а):
Да действительно так.


Вообще то это утверждение надо доказать строго. Чего то я стал сомневаться в истинности этого утверждения.

Обозначим Delacorte Number как D. Как D' обозначим число которое отличется от D:
Если a простое больше N*N/2 или равно 1, тогда Da,b=0 для всех b.

Утверждение. Если для некоторого квадрата D - максимальное(минимальное), тогда и D' максимальное(минимальное). И наоборот.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 17:53 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon в сообщении #916536 писал(а):
А еще он запретил обсуждения конкретных результатов.

А правила, опубликованные на сайте, этого не запрещают
Цитата:
You may post scores, so if you want to tell everyone that you got a raw score of 1,598,259 for n = 20 (whether true or not), go right ahead.


-- 08 окт 2014, 19:30 --

Pavlovsky в сообщении #916558 писал(а):
Обозначим Delacorte Number как D. Как D' обозначим число которое отличется от D:
Если a простое больше N*N/2 или равно 1, тогда Da,b=0 для всех b.

Утверждение. Если для некоторого квадрата D - максимальное(минимальное), тогда и D' максимальное(минимальное). И наоборот.

Определим для каждой пары $(a,b):\quad D^*_{a,b}=\mathrm{distance}^2(a, b)$, и $D^*$ как разность между числом Делакорта $D$ и суммой всех $D^*_{a,b}.$ Тогда верно следующее утверждение.

Утверждение: $D$ максимально (минимально) тогда и только тогда, когда максимально (минимально) $D^*.$

То есть пары с $\gcd(a,b)=1$ можно вставлять в последнюю очередь в произвольном порядке. В частности, это верно для простого $a>\frac{N^2}2$ и произвольного $b.$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 20:47 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #916612 писал(а):
То есть пары с $\gcd(a,b)=1$ можно вставлять в последнюю очередь в произвольном порядке.


Собственно, сформулированное мной утверждение, это попытка обосновать подобные алгоритмы. Попытка доказать утверждение, окончилась тем что скорее всего утверждение в общем случае неверно. Хотя есть содержательные частные случаи когда оно верно. Но об этом позже, нужно время на оформление.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.10.2014, 21:04 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #916735 писал(а):
Попытка доказать утверждение, окончилась тем что скорее всего утверждение в общем случае неверно.

Ваше утверждение следует из моего, а потому верно.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.10.2014, 03:09 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Проверил лемму экспериментальным образом. Лемма работает, по крайней мере для N<=6.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.10.2014, 07:33 
Аватара пользователя


21/02/10
1594
Екатеринбург
Для простоты изложения, пусть N=4.
Сформируем группы чисел.
2,4,6,8,10,12,14,16
3,6,9,12,15
4,8,12,16
5,10,15
6,12
7,14
8,16

Утверждение. Если можно заполнить квадрат 4х4 таким образом, что для каждой группы чисел сумма расстояний между ячейками минимально возможная. Тогда такое заполнение является минимально возможным решением.

Примеры фигур с минимально возможной суммой расстояний.
Количество чисел в группе=2
ХХ
=3
Х
ХХ
=4
ХХ
ХХ
=5
ХХ
ХХХ
=8
ХХ
ХХХ
ХХХ

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

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



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

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


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

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