Дьявольские магические квадраты из простых чисел

[whitefox]

Возьмём четыре попарно ортогональных покрытия, представленных Nataly-Mak.

В качестве главной диагонали возьмём: 3 7 67 83 163 181 251.
Её наименьший элемент поместим в левый верхний угол, а наибольший -- в правый нижний:

3 * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * 251

Из пересечения строки: 3 11 43 103 157 197 241,
и столбца: 17 37 53 71 103 223 251,
находим правый верхний угол -- 103. Аналогично находим левый нижний угол -- 19:

3 * * * * * 103
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
19 * * * * * 251

Из пересечения прямой диагонали: 3 7 67 83 163 181 251,
и обратной диагонали: 19 29 59 103 137 181 227,
найдём центр -- 181:

3 * * * * * 103
* * * * * * *
* * * * * * *
* * * 181 * * *
* * * * * * *
* * * * * * *
19 * * * * * 251

Через центр проходит строка: 13 41 71 109 167 173 181,
и столбец: 43 47 89 107 139 149 181.
С границами квадрата они пересекутся в точках: 43, 173, 71, 139:

3 * * 43 * * 103
* * * * * * *
* * * * * * *
173 * * 181 * * 71
* * * * * * *
* * * * * * *
19 * * 139 * * 251

Обратная диагональ: 37 43 67 113 131 173 191, пересечётся с главной диагональю в точке -- 67, а обратная диагональ: 11 71 73 83 139 179 199 -- в точке 83:

3 * * 43 * * 103
* 83 * * * * *
* * * * * * *
173 * * 181 * * 71
* * * * * * *
* * * * * 67 *
19 * * 139 * * 251

Продолжая в том же духе, заполним главную диагональ. А она однозначно определит весь квадрат. И всё это выполняется без какого-либо перебора.

[whitefox]

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

Необходимо: Сформулировать дополнительное условие (аксиому) гарантирующее укладку вышеописанной геометрии на торе.

Должна выполняться следующая аксиома (для нечётных N):

Классы параллельных прямых объединены в пары.
Пусть $a$ произвольная прямая, а $A$ и $B$ две различные точки этой прямой.
Также, пусть через точку $A$ проходит ещё прямая $b$, а через точку $B$ проходит прямая $c$, принадлежащие той же паре классов параллельных, но другому классу.
Пусть, также, через точку $A$ проходит прямая $d$, принадлежащая другой паре классов параллельных, и пересекающая прямую $c$ в точке $C$.
Пусть прямая $e$ проходит через точку $C$ и принадлежит тому же классу, что и прямая $a$, и пусть прямая $e$ пересекается с прямой $b$ в точке $D$.
Тогда через точки $D$ и $B$ проходит прямая $f$, принадлежащая той
же паре классов, что и прямая $d$, но другому классу этой пары.

-- 03 сен 2013, 13:21 --

Другая формулировка (опять же для нечётных N):

Классы параллельных прямых можно объединить в пары так, чтобы для любых четырёх точек A, B, C, D, таких что прямые AB и CD принадлежат одному классу параллельных, а прямые AC и BD другому классу параллельных из той же пары классов, прямая AD существует тогда и только тогда, когда существует прямая CB.

[whitefox]

Возможно, нужно сделать добавление (подчёркнуто):

Классы параллельных прямых можно объединить в пары так, чтобы для любых четырёх точек A, B, C, D, таких что прямые AB и CD принадлежат одному классу параллельных, а прямые AC и BD другому классу параллельных из той же пары классов, прямая AD, принадлежащая одному из классов второй пары, существует тогда и только тогда, когда существует прямая CB, принадлежащая другому классу той же пары.

[Pavlovsky]

А как нибудь попроще?
Если не ошибаюсь, например аксиома Фано гарантирует укладку конечной проективной плоскости в 2D евклидову плоскость.
http://ru.wikipedia.org/wiki/%CF%F0%EE% ... E%F1%F2%FC

[whitefox]

Pavlovsky
По Вашему определению, параллельные не пересекаются.
А в проективной плоскости пересекаются все прямые (аксиома П2 по Вашей ссылке).
Также в Вашей геометрии не выполнена и аксиома П1 (по указанной ссылке).
Поэтому к Вашей геометрии аксиома Фано не применима.

[Pavlovsky]

Теорему Фано это я так для примера. Почитал ваше условие, не такое оно уж и сложное. То есть проверить возможность построения пандиагонального квадрата из 4-х ортоганольных разбиений мы можем? Или что то упущенно?

[whitefox]

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

[mertz]

the Visual Studio project.

https://www.dropbox.com/s/3wt6c4ovafqug0d/Pan.zip

All of the code is in the file searchthread.cpp.

-- 03.09.2013, 05:25 --

And the linux version.

https://www.dropbox.com/s/e8asapbemn9alyq/Pan.tar.gz

[whitefox]

Опишу алгоритм построения пандиагонального магического квадрата из четырёх попарно ортогональных точных покрытий для N нечётного простого в терминах геометрии Pavlovsky.

Для определённости, обозначим, приведённую выше, аксиому как П3.

Нам дана геометрия Pavlovsky в которой выполнена аксиома П3.

Выберем произвольную пару классов параллельных (удовлетворяющих аксиоме П3) как пару точных покрытий для рядов (один из эти классов выберем как покрытие строк, а второй как покрытие столбцов). Оставшаяся пара классов определяет точные покрытия для диагоналей (один класс выберем для покрытия прямых диагоналей, а второй для обратных).

1. Выберем произвольную прямую диагональ и назовём её линией 1.
2. Выберем на линии 1 две произвольные различные точки -- точку 1 и точку 2.
3. Строку проходящую через точку 1 назовём линией 2.
4. Столбец проходящий через точку 2 назовём линией 3.
5. Точку пересечения линии 2 и линии 3 назовём точкой 3.
6. Обратную диагональ проходящую через точку 3 назовём линией 4.
7. Точку пересечения линии 1 и линии 4 назовём точкой 4.
8. Столбец проходящий через точку 4 назовём линией 5.
9. Точку пересечения линии 2 и линии 5 назовём точкой 5.
10. Строку проходящую через точку 2 назовём линией 6.
11. Точку пересечения линии 6 и линии 5 назовём точкой 6.
12. Обратную диагональ проходящую через точку 5 назовём линией 7.
13. Обратную диагональ проходящую через точку 6 назовём линией 8.
14. Точку пересечения линии 1 и линии 7 назовём точкой 7.
15. Точку пересечения линии 1 и линии 8 назовём точкой 8.
16. Точку пересечения линии 7 и линии 3 назовём точкой 9.
17. Столбец проходящий через точку 1 назовём линией 9.
18. Точку пересечения линии 8 и линии 9 назовём точкой 10.
19. Строку проходящую через точку 9 назовём линией 10.
20. Строку проходящую через точку 10 назовём линией 11.
21. Точку пресечения линии 10 и линии 1 назовём точкой 11.
22. Точку пересечения линии 11 и линии 1 назовём точкой 12.

Для N=7 точки 1,8,12,4,11,7,2 составляют главную диагональ пандиагонального квадрата и определяют этот квадрат однозначно (для больших N построение нужно продолжить).

Очевидно, что аксиомы П1, П2, П3 в совокупности обеспечивают успешность этого построения.

[Nataly-Mak]

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

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

Интересная постановка вопроса.
Как я поняла, whitefox проверяет возможность построения пандиагонального квадрата из полумагического (пара точных ортогональных покрытий):

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

Есть у меня программа следующая этому пути.

Начинает она свою работу со случайного выбора пары ортогональных покрытий (что эквивалентно случайному выбору полумагического квадрата). Делается это мгновенно.

Затем полным перебором проверяется -- существует ли пандиагональный квадрат, два покрытия которого совпадают с выбранными (то есть можно ли из данного полумагического квадрата получить пандиагональный). Перебор сильно оптимизирован, проверка выполняется очень быстро (примерно 700 пар покрытий за секунду для N=7).

Почему же мы не можем проверить "возможность построения пандиагонального квадрата из 4-х ортоганольных разбиений"?
По-моему, тут не должно быть вопроса. Конечно, проверить можем.

Однако речь в гипотезе whitefox шла не о проверке, а о том, что "возможность построения пандиагонального квадрата из 4-х ортоганольных разбиений" имеет место без всяких проверок.

Гипотеза

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

Допускаю возможность того, что из любых четырёх попарно ортогональных покрытий всегда можно составить пандиагональный квадрат, подобно тому как из пары ортогональных покрытий всегда составляется полумагический квадрат.

P.S. Кстати, о терминологии...
Хотелось бы прийти к общей терминологии, а не пользоваться каждый своей. Я этот вопрос почти в каждой теме поднимаю.
Pavlovsky пишет "4 ортогональных разбиения", whitefox пишет "4 точных попарно ортогональных покрытия". Если нашу дискуссию будет читать человек со стороны, он может ничего не понять: "разбиения", "покрытия"... У меня "цепочки", у whitefox "разбиения", что совсем не равно "разбиениям" Pavlovsky, которые "оротогональные разбиения".

[whitefox]

В своём предыдущем посте я привёл алгоритм построения пандиагонального квадрата по четырём ортогональным покрытиям, когда выполнена аксиома П3.

Но если нам не известно выполнена ли эта аксиома, то приведённое построение нужно выполнить максимум три раза. Так как из четырех покрытий можно составить пары тремя способами.

А гипотеза будет справедлива, если аксиома П3 является теоремой в геометрии Pavlovsky, что представляется маловероятным.

[Nataly-Mak]

Моя программа стабильно производит решения $S=733$ с 5-7 дырками.
В этих решениях нет элементов больше 239, и все элементы теперь получаются положительные. Вполне хорошие решения, похожи на реальные
Покажу два решения с 5 дырками:

11  115*  197  191  163  53*  3 
 67  97  17  29  181  131  211 
 157  187*  71  13  59  107  139 
 151  31  211*  199  79*  43  19 
 61  23  127  109  193  167  53 
 173  101  37  103  7  83  229 
 113  179  73  89  51*  149  79

11  137  197  191  163  31*  3 
 67  97  17  29  181  131  211 
 157  165*  71  13  59  129*  139 
 151  31  233  199  57*  43  19 
 61  23  127  109  193  167  53 
 173  101  37  103  7  83  229 
 113  179  51*  89  73  149  79 

В подсчёте дырок возможны ошибки, у меня программа дырки не считает, я их считаю вручную.
По программе mertz у меня получаются только решения с 3 дырками (с 2 дырками никак); если учесть, что в каждом таком решении есть элемент больше 239, то дырок по сути дела 4, так как числа бОльшие 239 в реальном решении присутствовать не могут.

Строго говоря, во втором из показанных решений 6 дырок, так как числа 229 и 233 не могут одновременно присутствовать в реальном решении.

P.S. Ба, в первом решении тоже 6 дырок насчитала Всё, надо идти спать, глаза уже слипаются, дырки не вижу

[dimkadimon]

Вот мои результаты. Искал 749 6 дней и так не нашёл, зато нашёл 1138 решений с одной ошибкой. Теперь начал искать 743, пока нашёл 58 решений с одной ошибкой.

[Nataly-Mak]

dimkadimon
а вы в курсе, что решение $S=749$ найдено?

Цитата:

7x7 749 Wes Sampson
La Jolla, California, United States 30 Aug 2013 01:24

(3,53,167,103,181,31,211), (157,109,61,227,5,59,131), (79,151,101,23,89,193,113), (41,107,83,127,241,13,137), (97,269,73,71,37,191,11), (199,17,67,179,47,233,7), (173,43,197,19,149,29,139)

[dimkadimon]

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

а вы в курсе, что решение $S=749$ найдено?

Да