2014 dxdy logo

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

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




На страницу Пред.  1 ... 22, 23, 24, 25, 26, 27, 28 ... 67  След.
 
 Re: Prime Sums
Сообщение14.11.2012, 05:13 
Аватара пользователя
Gerbicz
как автор темы, ещё раз призываю вас прекратить оффтоп.
Здесь у нас научный форум, раздел "Программирование", тема о задаче конкурса именно с точки зрения программирования.
Всё, что вы пишете, является оффтопом, не имеющим никакого отношения ни к задаче конкурса, ни к программированию.
Ваши претензии вы можете обсудить на сайте конкурса, там ведь есть форум, или же в личной переписке с администратором конкурса.

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

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

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

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 05:16 
Аватара пользователя
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.

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

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 08:50 
Аватара пользователя
Сейчас легко нашёл 504 и 784 для N=5. А вот 506 не вижу пока...
Вполне возможно, что такого решения не существует.

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 09:27 
Аватара пользователя

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

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

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

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

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 13:44 
Аватара пользователя
Рассмотрим два решения для 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). Для задачи текущего конкурса такой фундаментальной статьи пока нет (или я просто о ней не знаю?).

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 13:53 
Аватара пользователя
Nataly-Mak в сообщении #644434 писал(а):
На мой взгляд, эти две схемы неизоморфны. Могу ошибаться.


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

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

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

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 13:56 
Аватара пользователя
Не только количество четвёрок; в них вообще все веса в разных количествах присутствуют. Именно поэтому я и сделала вывод, что схемы неизоморфны.

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 14:00 
Аватара пользователя
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 не существует.

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 14:12 
Аватара пользователя
В статье Россера (ссылка есть в этой теме) есть теоремы 4.3 и 4.4. Которые описывают группу изоморфизмов пандиагонального квадрата.

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

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

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

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

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 14:23 
Аватара пользователя
Пандиагональный квадрат остаётся пандиагональным, если к нему применить преобразование "взятие дополнения". Квадраты конкурсной задачи не составляют группу изоморфизма относительно данного преобразования.

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 14:24 
Аватара пользователя
Для 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$, либо сама структура симметрична.

 
 
 
 Re: Prime Sums
Сообщение14.11.2012, 14:40 
Аватара пользователя
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$, либо сама структура симметрична.


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

 
 
 [ Сообщений: 1005 ]  На страницу Пред.  1 ... 22, 23, 24, 25, 26, 27, 28 ... 67  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group