Al Zimmerman - Delacorte Numbers

[dimkadimon]

Стартовал новый конкурс Al Zimmerman - Delacorte Numbers. http://www.azspcs.net/Contest/DelacorteNumbers

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

[Pavlovsky]

Ссылки на статьи по теме есть?

[dimkadimon]

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

Ссылки на статьи по теме есть?

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

[dimkadimon]

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

[Herbert Kociemba]

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.

[dimkadimon]

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.

[Pavlovsky]

dimkadimon в сообщении #916120 писал(а):

Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.

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

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

[whitefox]

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

dimkadimon в сообщении #916120 писал(а):

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

Скорее это лемма, чем аксиома.

[dimkadimon]

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 можно вообще не использовать при заполнении квадрата. А после заполнения квадрата другими числами, заполнить ими свободные места, порядок при этом не важен.

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

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

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

[Pavlovsky]

dimkadimon в сообщении #916536 писал(а):

Да действительно так.

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

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

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

[whitefox]

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

[Pavlovsky]

whitefox в сообщении #916612 писал(а):

То есть пары с $\gcd(a,b)=1$ можно вставлять в последнюю очередь в произвольном порядке.

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

[whitefox]

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

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

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

[dimkadimon]

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

[Pavlovsky]

Для простоты изложения, пусть 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
ХХ
ХХХ
ХХХ