Prime Sums

[whitefox]

Nataly-Mak
Приведённый в Вашей статье пример соответствует композиции двух преобразований Россера:

$$Q=\begin{Vmatrix} 1 & 1 \\1 & -1 \end{Vmatrix}\text{, и }S_{2}=\begin{Vmatrix} 2 & 0 \\ 0 & 2 \end{Vmatrix}\text{, так как }(2,5)=1$$

-- 14 ноя 2012, 23:34 --

Преобразование Россера $Q$ фактически делает тоже самое, что и:

svb в сообщении #644727 писал(а):

Для нечетных N можно поменять диагонали с горизонталями/вертикалями с помощью $S = \left\| {\begin{array}{*{20}c} 1 & 1 \\ { - 1} & 1 \\ \end{array}} \right\|$

[Nataly-Mak]

whitefox
можно показать подробно результат первого преобразования и результат второго?
Я плохо понимаю вашу форму записи преобразований

-- Ср ноя 14, 2012 23:55:06 --

Взяла вот это решение для 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

[решение выложено на форуме конкурса, если что ]

Применила к этому квадрату 5х5 своё преобразование "строки-диагонали", описанное матрицей в указанной статье, и получила решение с таким же результатом 766:



Как получить композицией преобразований Россера такой квадрат из исходного квадрата?

[whitefox]

Форма записи не моя, а Россера.

$$T=\begin{Vmatrix} a &c\\b&d\end{Vmatrix}$$

Означает, что квадрат $A$ преобразуется в квадрат $B$ по правилу:

$$B(i',j')=A(ai+cj,bi+dj)$$

В прошлом посте я ошибся, вместо преобразования Россера $Q$ нужно взять преобразование $Q'=\begin{Vmatrix} -1 &1\\-1&-1\end{Vmatrix}$.

Сначала применим преобразование $Q'$, получим матрицу индексов:

00 14 23 32 41
44 03 12 21 30
33 42 01 10 24
22 31 40 04 13
11 20 34 43 02

Теперь применим преобразование $S_2$, получим:

00 23 41 14 32
33 01 24 42 10
11 34 02 20 43
44 12 30 03 21
22 40 13 31 04

Что полностью соответствует матрице индексов Вашего преобразования "строки диагонали".

[svb]

Преобразования Россера это аналог преобразований плоскости, но рассматриваемых на целочисленных точках тора. Чтобы сохранить все 4 группы рассматриваемых линий можно плоскость "раздувать" (умножение на число), поворачивать на 45 или 90 градусов, симметрично отражать. Все это описывается с помощью матриц 2x2. Если рассматривать все аффинные преобразования, то необходимо еще добавить сдвиги.

Преобразование Nataly-Mak, конечно, связано с поворотом на 45 градусов, т.к. только после такого поворота строки переходят в диагонали и наоборот.

[Nataly-Mak]

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

...Что полностью соответствует матрице индексов Вашего преобразования "строки диагонали".

Спасибо большое, теперь всё поняла.

А преобразование $S_2$ есть не что иное как перестановка строк с постоянным шагом с последующей перестановкой столбцов с тем же шагом.
Такие преобразования пандиагональных квадратов я тоже рассматривала в своих статьях. Можно поискать примеры.

А в данном конкретном примере имеем исходный квадрат:

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

Применим к нему преобразование $S_2$.
Первый этап - переставляем в этом квадрате строки с шагом 1 (у меня такая терминология, "с шагом 1" означает через одну строку или через один столбец):

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

Второй этап: переставляем в полученном квадрате столбцы тоже с шагом 1:

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

И готово новое изоморфное решение! Проверила в программе Эда, тот же результат 766.

Попробую применить преобразование $S_3$ к тому же исходному квадрату. Теперь будем переставлять строки с шагом 2 и потом столбцы тоже с шагом 2.
Первый этап - переставляем в исходном квадрате строки:

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

второй этап - переставляем в полученном квадрате столбцы:

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

Правильно применила преобразование $S_3$ ?

Сейчас проверю полученное изоморфное решение в программе Эда.

И преобразование $S_4$ можно применить, так как 4 и 5 тоже взаимно просты.

-- Чт ноя 15, 2012 06:40:18 --

Проверила в программе Эда решение, полученное преобразованием $S_3$, всё верно, получилось решение с тем же результатом 766, вот оно:



whitefox
вы по-прежнему не видите мои картинки?

-- Чт ноя 15, 2012 06:56:45 --

До кучи решение, полученное из того же исходного квадрата преобразованием $S_4$:

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

Тут у меня получился просто параллельный сдвиг на торе по обеим осям.
Решение даёт тот же результат 766.

[Pavlovsky]

svb в сообщении #644595 писал(а):

Всего можно провести 4N линий, которым соответствует матрица пересечений из одних 4. Выбору 2N линий некоторой схемы соответствует дополнительная схема из 2N не выбранных линий. Сумма матриц пересечений этих двух схем равна матрице из 4.

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

Также очевидно, что нижние и верхние оценки этих схем соответственно равны. То есть Вы уже доказали теорему, которую взялся доказывать Pavlovsky

Хорошая получилась теорема. Схемы из 2N линий и из оставшихся 2N линий имеют одинаковые оценки! Надо подумать как использовать этот факт.

PS Мини провокация удалась. Когда я пригрозил, что все брошу и буду доказывать теорему, на сам деле я надеялся, что кто то это сделает быстрее.

[Nataly-Mak]

В десятке сильнейших затишье:

Цитата:

1 Vladimir Chirkov 50.000000 11-10-2012 @ 15:20:54
2 Wes Sampson 49.993000 11-07-2012 @ 01:52:19
3 Dmitry Kamenetsky 49.990800 11-01-2012 @ 04:17:50
4 Alex Chernov 49.990800 11-04-2012 @ 20:18:58
5 Robert Gerbicz 49.986400 10-23-2012 @ 22:11:05
6 Herbert Kociemba 49.986400 11-03-2012 @ 13:09:12
7 Serg Belyaev 49.985100 10-31-2012 @ 22:12:29
8 Rick Hennig 49.965700 11-09-2012 @ 21:36:29
9 Ed Mertensotto 49.958700 11-13-2012 @ 19:15:39
10 Kendrick Boyd 49.957000 10-30-2012 @ 19:26:21

Кстати, что-то многовато здесь американцев, аж 4 человека.
Как-то неожиданно (говоря языком Gerbicz).

Да, наверное, рекорды для N=6,7 очень не просто даются
Тем ценнее результаты нашего Владимира!
Но не будем расслабляться и заранее праздновать победу. До конца конкурса ещё очень далеко, хотя и сократили его почти на полмесяца.
Правильно сделали, что сократили. Я всегда говорила, что 3 месяца - это очень много для любого конкурса. По мне бы и ещё полмесяца урезать, двух месяцев более чем достаточно.
Активность конкурсантов резко упала. Многие вообще бросили задачу в октябре. Возникает вопрос: почему бросили? Тут, конечно, много разных причин может быть. Но главная причина, как мне кажется, отсутствие стойкого интереса к задаче.

У меня напрочь пропал интерес к задаче. Завершаю второй "круг почёта" и на этом, пожалуй, закругляюсь. Мой потолок - 46 баллов с хвостиком.

[Pavlovsky]

Подведу итоги.

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

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

С помощью преобразований Россера. И преобразования взятия дополнения, сохраняющего суммы в заданных 2N линиях. В этом направлении можно еще покопать. Поискать другие преобразования, сохраняющие суммы в заданных 2N линиях. Можно существенно сократить количество неизоморфных схем.

В качестве 2N простых чисел можно брать последний набор среди наборов упорядоченных в лексикографическом порядке.

Осталось совсем немного. Задать соответсвие между 2N линиями схемы и 2N простыми числами. И заполнить квадрат согласно этому соответсвию.

[Nataly-Mak]

Одну из 6034 схем с оценкой 1802 уже нашёл Vovka17. Здорово! Классный результат.
Осталось всего два шага - результаты 1800 и 1798. Осилит ли кто-нибудь? Тоже жар-птица

[Pavlovsky]

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

Одну из 6034 схем с оценкой 1802 уже нашёл Vovka17

Чтобы получить результат 1802 можно использовать схемы с меньшей оценкой. 4800+516+6034=11350. Получается много. Так что задача отбросить изоморфные схемы для N=7 актуальна.

-- Чт ноя 15, 2012 09:57:12 --

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

Как-то неожиданно

Это разве неожиданно?! А вот за два дня пригнуть на 34-е место. Вот это действительно вызывает уважение.

Цитата:

34 Daniel Ugra 37.778800 11-14-2012 @ 17:07:56

[Nataly-Mak]

Кстати:

Vovka17 в сообщении #642707 писал(а):

Семерка ещё сложнее. Пока оставил на работе пару компьютеров для обсчета семерки. В понедельник будет результат, или не будет, что тоже результат.

Vovka17
и какой же был результат

-- Чт ноя 15, 2012 09:07:51 --

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

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

Как-то неожиданно

Это разве неожиданно?!

Это был просто прикол

Цитата:

А вот за два дня пригнуть на 34-е место. Вот это действительно вызывает уважение.

Цитата:

34 Daniel Ugra 37.778800 11-14-2012 @ 17:07:56

Ну, это нисколько не удивительно.
dimkadimon, например, за два дня прыгнул на второе место.
А Gerbicz тоже за два дня (или за три что ли) прыгнул на первое место.

-- Чт ноя 15, 2012 09:17:29 --

Или вот:

Цитата:

40 Artem Ripatti 32.926100 10-14-2012 @ 11:53:28

Обратите внимание на дату! Два дня шёл конкурс.
И у него было 24-ое место, отлично помню. А сейчас уже только 40-ое, потому что бросил задачу.

[whitefox]

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

whitefox
вы по-прежнему не видите мои картинки?

Увы.
Более того, когда вчера читал Вашу статью, то обнаружил, что и там не все картинки мне видны.
Но ведь раньше я видел их все.

[svb]

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

Хорошая получилась теорема. Схемы из 2N линий и из оставшихся 2N линий имеют одинаковые оценки! Надо подумать как использовать этот факт.

Оценки то одинаковые, но ... С точки зрения конкурсной задачи это мало что дает.

2N линий, рассматриваемые как ребра графа, интересны для последующего заполнения числами. Эквивалентными схемами разумно считать такие, которым соответствуют одинаковые графы. Ясно, что рассмотренные выше "преобразования Россера" не меняют исходного графа, но существуют ли иные схемы с одинаковыми графами?

Pavlovsky

Чтобы получить результат 1802 можно использовать схемы с меньшей оценкой. 4800+516+6034=11350. Получается много. Так что задача отбросить изоморфные схемы для N=7 актуальна.

Я попробовал перебор для одной случайно выбранной схемы - через несколько часов остановил программу Еще добавить перебор по схемам?
Для N=5,6 помог элементарный случай. В дальнейшем много раз тестировал версии программы на этих значениях N и, хотя иногда повторяю рекорды, картинка меня не радует. Вот для N>7 программа уже стала "летать". Сейчас вообще перестал перебирать, надо подумать

[Nataly-Mak]

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

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

whitefox
вы по-прежнему не видите мои картинки?

Увы.
Более того, когда вчера читал Вашу статью, то обнаружил, что и там не все картинки мне видны.
Но ведь раньше я видел их все.

Вот насчёт картинок на форуме действительно непонятно. Почему все видят, а вы не видите? На форуме есть раздел "Работа форума". Может, вам там задать этот вопрос.

А в статье да, что-то там с картинками не совсем в порядке. У меня хотя картинки и видны все, но некоторые лилипуты совсем
Всё течёт, всё изменяется. Статья написана давно. В то время, когда она писалась, все картинки были на месте и все были нормального размера.
Сейчас у меня другой компьютер, значит, новый браузер, поэтому такие фокусы с лилипутными картинками. Я в эту статью сто лет уже не заглядывала. Вот вчера по случаю заглянула.
Опять же непонятно: почему одни картинки имеют нормальный размер, а другие лилипуты?

[Pavlovsky]

svb в сообщении #644834 писал(а):

Я попробовал перебор для одной случайно выбранной схемы - через несколько часов остановил программу Еще добавить перебор по схемам?

Уже неделю исследую задачу для N=7. Есть подвижки, но пока их недостаточно. И прихожу к выводу, что не все схемы одинаково хороши. Все таки попробую найти все неизоморфные схемы, чтобы посмотреть их различные свойства.
Для N>7 у меня практически все готово. Надо кодить. Уверенность в успехе поиска рекордных результатов для N>7 настолько велика, что это задача мне уже не интересна.