Prime Sums

[Nataly-Mak]

Gerbicz
как автор темы, ещё раз призываю вас прекратить оффтоп.
Здесь у нас научный форум, раздел "Программирование", тема о задаче конкурса именно с точки зрения программирования.
Всё, что вы пишете, является оффтопом, не имеющим никакого отношения ни к задаче конкурса, ни к программированию.
Ваши претензии вы можете обсудить на сайте конкурса, там ведь есть форум, или же в личной переписке с администратором конкурса.

Мы будем здесь обсуждать математику задачи, алгоритмы её решения, и никто нам не может это запретить. Это независимый форум.
А если администратор конкурса считает, что кто-то из конкурсантов нарушил Правила, он будет принимать меры. Но всё это будет обсуждаться не здесь.

Пожалуйста, не зафлуживайте тему! Это является нарушением Правил данного форума.

Такая же просьба к коллегам: пожалуйста, не поддерживайте развитие оффтопа.

[dimkadimon]

Gerbicz в сообщении #644317 писал(а):

That would be a 24 pages long proof (the current size of this forum). Though shorter than the proof of the classification of finite simple groups. Moreover I don't like to receive such a long email, probably Neil feels the same.

How is this a proof? Discussion of the problem is allowed. No solutions or code have been discussed in this forum. So please stop your meaningless accusations.

[Nataly-Mak]

Проверила все свои решения для N=5, у меня их более тысячи. Интересно, что нет ни одного решения с результатами: 504, 506 и 784. Все остальные решения в диапазоне 502 - 790 есть.
dimkadimon сообщал, что решение с результатом 504 имеется.
Имеются ли решения с результатами 506 и 784

[Vovka17]

Сейчас легко нашёл 504 и 784 для N=5. А вот 506 не вижу пока...
Вполне возможно, что такого решения не существует.

[whitefox]

(2Gerbicz)

Gerbicz в сообщении #644285 писал(а):

"This is his response to the message that the first version of Ed does not correctly handle duplicates"
I thought that you are speaking about the online scorer. I haven't downloaded Ed's program, so not used. I've used my own, probably much better and faster scorers.

Оказывается и на Солнце есть пятна.

Выходит, уважаемый Gerbicz, Вы тоже можете заблуждаться?

А не допускаете ли Вы, что и все Ваши обвинения тоже заблуждение?

[Nataly-Mak]

Рассмотрим два решения для N=5 с результатом 766.

Первое решение (выложено на форуме конкурса, если что):

25,24,21,20,23,19,9,1,13,11,18,6,15,7,10,17,16,3,4,5,22,12,14,2,8

Схема этого решения:

3 4 1 2 3
4 3 2 2 2
2 1 2 1 1
1 3 1 2 1
3 1 2 1 1

Второе решение (моё):

9,21,20,8,15,18,4,22,1,11,10,2,14,5,25,6,3,17,13,12,23,19,24,7,16

Схема этого решения:

2 3 4 1 3
2 1 2 1 2
1 1 1 2 3
1 1 3 1 3
2 3 3 3 2

На мой взгляд, эти две схемы неизоморфны. Могу ошибаться.
Получается, что две неизоморфные схемы дают одинаковый результат.
Какие схемы являются изоморфными? Сколько неизоморфных схем имеют оптимальные решения?

Схемы (конфигурации) ждут своего исследователя. Нужна классификация конфигураций, определение изоморфизма конфигураций. Всё это надо хорошо исследовать, написать фундаментальную статью типа той, что написана по раскраскам (статья №1). Для задачи текущего конкурса такой фундаментальной статьи пока нет (или я просто о ней не знаю?).

[Pavlovsky]

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

На мой взгляд, эти две схемы неизоморфны. Могу ошибаться.

Естественно неизоморфны. Например количество 4-ок в них различное.

-- Ср ноя 14, 2012 15:55:51 --

У схем изоморфные преобразования такие же как у квадратов.
1) Перемещение на торе
2) Зеркальное отражение относительно диагоналей квадрата или повороты на 90 градусов.

[Nataly-Mak]

Не только количество четвёрок; в них вообще все веса в разных количествах присутствуют. Именно поэтому я и сделала вывод, что схемы неизоморфны.

[whitefox]

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

У схем изоморфные преобразования такие же как у квадратов.
1) Перемещение на торе
2) Зеркальное отражение относительно диагоналей квадрата или повороты на 90 градусов.

Добавим ещё зеркальные отражения относительно вертикали и относительно горизонтали.

-- 14 ноя 2012, 15:12 --

Для N=5 существуют следующие количества не изоморфных схем:
482 - 38
484 - 224
488 - 40
490 - 96
491 - 24
492 - 68
495 - 80
498 - 72
499 -16
500- 132
502 - 72

Других схем с оценкой не больше 502 не существует.

[Pavlovsky]

В статье Россера (ссылка есть в этой теме) есть теоремы 4.3 и 4.4. Которые описывают группу изоморфизмов пандиагонального квадрата.

Теорема 3.4. Группа G имеет порядок 4n^2*Fi(n), если n четно и 8n^2*Fi(n) , если n
нечетно. Fi(n) это число целых чисел меньше чем n и взаимно простых с n .

Чего то в нашем списке преобразований не хватает.

[whitefox]

Для N=6 существует всего шесть не изоморфных схем с оценкой не больше 890.
Все эти схемы имеют оценку 887, и три из них имеют структуру: 4,10,9,8,5, а три другие структуру: 5,8,9,10,4 (обратную первой).

[Pavlovsky]

8n^2*Fi(n) для n=5 дает 32*n^2 преобразований. n^2 это перенос на торе. Значит есть еще 5 бинарных преобразования, которые неэквиавелнтны друг другу. Под бинарным преобразованием понимаю преобразование, такое что если мы применим его дважды, то получим исходный квадрат. Ну типа преобразования зеркального отражения относительно диагонали.

[Nataly-Mak]

Пандиагональный квадрат остаётся пандиагональным, если к нему применить преобразование "взятие дополнения". Квадраты конкурсной задачи не составляют группу изоморфизма относительно данного преобразования.

[whitefox]

Для N=7 существуют следующие количества не изоморфных схем с оценкой не более 1806:
1798 - 4800
1800 - 516
1802 - 6034
1804 - 5538
1806 - 144

-- 14 ноя 2012, 15:28 --

Для N=8 имеется всего 39 не изоморфных схем с оценкой не более 2752.
Все они имеют оценку ровно 2752 и структуру: 8,16,16,16,8.

-- 14 ноя 2012, 15:35 --

Интересный факт: во всех приведённых случаях каждой схеме со структурой $a_1,a_2,a_3,a_4,a_5$ соответствует схема со структурой $a_5,a_4,a_3,a_2,a_1$, либо сама структура симметрична.

[Pavlovsky]

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

Добавим ещё зеркальные отражения относительно вертикали и относительно горизонтали.

Все равно мало. Скажем, для n=5, согласно Россеру должно быть еще одно преобразование.

-- Ср ноя 14, 2012 16:42:03 --

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

Интересный факт: во всех приведённых случаях каждой схеме со структурой $a_1,a_2,a_3,a_4,a_5$ соответствует схема со структурой $a_5,a_4,a_3,a_2,a_1$, либо сама структура симметрична.

А это похоже преобразование, не описанное Россером. Надо пожалуй потратить время и сделать из этой гипотезы теорему.