Магические квадраты

[Nataly-Mak]

Бродила по Интернету в поисках нетрадиционных пандиагональных квадратов. Таких не нашла. Но вот нашла интересный сайт о магических квадратах, я такой ещё не видела. На нём, кстати, есть квадраты из последовательных простых чисел, построенные японцем A. Suzuki.

http://mathforum.org/te/exchange/hosted ... quare.html

[Nataly-Mak]

Да, товарищи, с вами не соскучишься
Ну, я и не скучаю.
Вот решила посмотреть, а что у нас в пандиагональных квадратах 8-го порядка. Построенный мной пандиагональный квадрат данного порядка из простых чисел с магической константой 2640 составлен по решётке Россера из 4-х пандиагональных квадратов 4-го порядка с одинаковой магической константой и потому состоит из 32 комплементарных пар.
А ведь наверняка можно составить пандиагональный квадрата из псевдокомплементарных пар, так же как и пандиагональный квадрат 6-го порядка.
Взяла давно построенный классический идеальный квадрат 8-го порядка:

1 32 41 56 49 48 25 8
63 34 23 10 15 18 39 58
4 29 44 53 52 45 28 5
62 35 22 11 14 19 38 59
6 27 46 51 54 43 30 3
60 37 20 13 12 21 36 61
7 26 47 50 55 42 31 2
57 40 17 16 9 24 33 64

Этот квадрат вообще-то тоже составлен из 32 комплементарных пар, но можно посмотреть на него в другом ракурсе:

p1 p2 p3 p4 p1 p2 p3 p4
-p1 -p2 -p3 -p4 -p1 -p2 -p3 -p4
-p3 -p4 -p1 -p2 -p3 -p4 -p1 -p2
-p4 -p3 -p2 -p1 -p4 -p3 -p2 -p1
p1 p2 p3 p4 p1 p2 p3 p4
-p1 -p2 -p3 -p4 -p1 -p2 -p3 -p4
-p3 -p4 -p1 -p2 -p3 -p4 -p1 -p2
-p4 -p3 -p2 -p1 -p4 -p3 -p2 -p1

Имеем 4 группы псевдокомплементарных пар с отклонениями p1, p2, p3, p4 и 4 группы с обратными отклонениями -p1, -p2, -p3, -p4. При этом отклонения должны быть связаны так: p1 = -p2, p3 = -p4. То есть фактически надо всего 4 группы псевдокомплементарных пар - с отклонениями p1, -p1, p3, -p3.
В каждой группе должно быть не менее 8 пар.

Для приведённого квадрата имеем такие отклонения от комплементарности:
p1 = 10, p2 = -10, p3 = -6, p4 = 6.

Возможно, такая конфигурация - частный случай, так как рассматриваемый классический квадрат идеальный. Но, как мне кажется, всё в этой конфигурации правильно.

svb
как вы оцените эту конфигурацию? Она правильная?
Интересно, можно ли составить по такой конфигурации пандиагональный квадрат из простых чисел?

Кстати, интересный критерий для всех подобных конфигураций пандиагональных квадратов чётных порядков: квадрат, составленный из отклонений, должен быть пандиагональным квадратом с магической константой равной 0.
Вот, например, квадрат, составленный из отклонений известного пандиагонального квадрата 6-го порядка из последовательных простых чисел:

-14 34 -60 14 -34 60
-70 50 -24 70 -50 24
10 10 -36 -10 -10 36
14 -34 60 -14 34 -60
70 -50 24 -70 50 -24
-10 -10 36 10 10 -36

Теперь совсем понятно, откуда взялись условия для отклонений

-- Вс сен 19, 2010 04:59:57 --

В качестве иллюстрации приведён пандиагональный квадрат 8-го порядка из простых чисел, построенный по решётке Россера из 4-х пандиагональных квадратов 4-го порядка:

61 137 103 229 503 311 653 643
47 73 193 251 449 379 631 617
509 313 647 641 67 139 97 227
461 389 619 607 59 83 181 241
157 349 7 17 599 523 557 431
211 281 29 43 613 587 467 409
593 521 563 433 151 347 13 19
601 577 479 419 199 271 41 53

Этот квадрат тоже вписывается в приведённую конфигурацию, только в этом случае все отклонения от комплементарности равны 0.
Константа комплементарности для квадрата 8-го порядка S_c = S/4, где $S$ - магическая константа квадрата. Для приведённого квадрата S_c = 660.

[Nataly-Mak]

Очень стало любопытно, что может получиться с приведённой конфигурацией для пандиагонального квадрата 8-го порядка.
svb молчит, не даёт оценку конфигурации

Решила сама попробовать. Взяла минимально возможную магическую константу для квадрата 8-го порядка из простых чисел - 1152. Отклонения выбрала такие: p_1 = 6, p_3 = 12. Группы псевдокомплементарных пар получились хорошие, от 16 до 21 пары чисел.
В точной аналогии с пандиагональным квадратом 6-го порядка начинаю писать программу. Вот первый этап, программа формирует две строки:

11  5  7  263  271  251  241  103 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 
 23  31  59  173  283  277  293  13 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0

С двух строк я начинала и в квадрате 6-го порядка. Но! Там переменных меньше, всего 12, а здесь насчитала 24 независимых переменных. Это то, что называется экспоненциальным взрывом.
Вот для формирования только двух строк уже задействованы 7 свободных переменных. Следующий этап - формируются два столбца, ещё 5 свободных переменных. И так далее. Удастся ли преодолеть такое количество вложенных циклов?

А сколько в общей формуле пандиагонального квадрата 8-го порядка свободных переменных?
svb где-то приводил формулу, но я её забыла, а искать очень долго.
Ну, может быть, он придёт наконец и что-нибудь скажет

[Nataly-Mak]

Второй этап программа выполняет легко:

11  5  7  263  271  229  269  97 
 41  0  0  0  71  0  0  0 
 257  0  0  0  43  0  0  0 
 239  0  0  0  163  0  0  0 
 23  53  31  179  283  277  293  13 
 211  0  0  0  241  0  0  0 
 233  0  0  0  19  0  0  0 
 137  0  0  0  61  0  0  0

А это уже задействовано 12 независимых переменных! Осталось чуть-чуть ровно 12 переменных. Нет, конечно, это, наверное, не вытянет программа. Ну, разве только в конце разрешить повторение чисел. Но как красиво всё получается!

[svb]

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

svb молчит, не даёт оценку конфигурации

Из Россера следует, что для всех четных порядков нужно рассматривить решетки $L(2)$, т.е. производить разбивку на 4 квадрата аналогично случаю 6-го порядка с привлечением понятия "псевдокомплементарности". Но вот распространение подобной разбивки на каждый из входящих 4-х квадратов это уже завышенное требование, хотя, конечно, и допустимо, т.к. позволяет сузить поиск.

Цитата:

А сколько в общей формуле пандиагонального квадрата 8-го порядка свободных переменных?
svb где-то приводил формулу, но я её забыла, а искать очень долго.
Ну, может быть, он придёт наконец и что-нибудь скажет

Для четных порядков число свободных переменных (без учета магической суммы) равно $(N-2)^2$, т.е. 36 для 8-го порядка.Кстати, до сих пор не могу найти простого доказательства этому, хотя с "практической" точки зрения это и очевидно.

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

[svb]

Покрутил 8-й порядок:

 p1   p2   p3   p4  -p1  -p2  -p3  -p4
 p5   p6   p7   p8  -p5  -p6  -p7  -p8
 p9   pA   pB   pC  -p9  -pA  -pB  -pC
 pD   pE   pF   pG  -pD  -pE  -pF  -pG
-p1' -p2' -p3' -p4'  p1'  p2'  p3'  p4'
-p5' -p6' -p7' -p8'  p5'  p6'  p7'  p8'
-p9' -pA' -pB' -pC'  p9'  pA'  pB'  pC'
-pD' -pE' -pF' -pG'  pD'  pE'  pF'  pG'

При этом независимыми можно выбрать p1,p2,...,p8, остальные выглядят так:

     p1         p2         p3         p4
     p5         p6         p7         p8
 -p1-p6+p8  -p2-p5-p7  -p3-p6-p8  -p4+p5-p7
  p2-p4+p5   p1+p3+p6   p2+p4+p7  -p1+p3+p8

[svb]

Что-то не так. Когда стал считать независимые переменные, то никак не мог выйти на 36. Потом наконец дошло в чем ошибка. Почему то под решеткой $L(2)$ я имел в виду 4-ки чисел, которые на самом деле представляют собой решетку $L(4)$. А ведь про решетку $L(4)$ мы не можем ничего сказать о сумме ее элементов, как в случае решеток $L(2)$ и $L(3)$. Более того, при рассмотрении квадратов 6-го порядка именно решетки $L(3)$, а не $L(2)$ позволили ввести "псевдокомплементарность" - хорошо хоть рассуждения о квадратах 6-го порядка не развалились Весьма неожиданный удар, да уж ... Но тем интереснее!

[Nataly-Mak]

Вы ничего не сказали о моей конфигурации для пандиагонального квадрата 8-го порядка. Она ведь совсем не такая, какую вы представили.
А я уже программу писать начала.

Да, вот распишу подробнее. Выше конфигурация представлена в обозначениях груп p_i. У меня всего 4 группы: с отклонениями p_1, -p_1, p_3, -p_3. Обозначим элементы этих групп: a_i, b_i, c_i, d_i, i = 1, 2, ..., 8 соответственно. Тогда конфигурация, заполненная элементами групп, будет иметь следующий вид:

a1 b1 c1 d1 a5 b5 c5 d5
b2 a2 d2 c2 b6 a6 d6 c6
d3 c3 b3 a3 d7 c7 b7 a7
c4 d4 a4 b4 c8 d8 a8 b8
a5' b5' c5' d5' a1' b1' c1' d1'
b6' a6' d6' c6' b2' a2' d2' c2'
d7' c7' b7' a7' d3' c3' b3' a3'
c8' d8' a8' b8' c4' d4' a4' b4'

при этом
a_i + a_i' - S_c = p_1, b_i + b_i' - S_c = -p_1, c_i + c_i' - S_c = p_3, d_i + d_i' - S_c = -p_3
где S_c - константа комплементарности.

Я спрашивала вас, верная ли эта конфигурация, так как плохо разобралась с решётками Россера, а эту конфигурацию сочинила из классического идеального квадрата 8-го порядка.
Мне кажется, что всё правильно.

Итак, значит, в общей формуле для пандиагонального квадрата 8-го порядка 36 свободных переменных из 64, это уже больше половины получается. Много! Вот приведённая конфигурация уменьшает количество свободных переменных на 12, их всего 24. Но и тут я сомневаюсь в том, что для компьютера это реально. Можно ли за реальное время выполнить 24 вложенных цикла, переменные которых пробегают от 32 до 42 значений?
На примере построения пандиагонального квадрата 6-го порядка мы убедились, что можно выполнить 16 вложенных циклов, переменные которых пробегают 36 значений; на это программе maxal'а понадобилось 12 часов. При этом надо ещё учесть, что решение могло найтись гораздо раньше, чем отработали все вложенные циклы полностью. А вот если решения не существует, придётся программе выполнить все циклы полностью, на что потребуется ещё больше времени.
Так что тут опять надо думать и думать. К сожалению, вот этого-то компьютер делать и не умеет

Интересно взять все эти пары простых чисел (я их все, конечно, нашла, так как программу пишу с конкретными парами), забыть про компьютер и программы и попытаться составить пандиагональный квадрат 8-го порядка, используя только голову и руки. Как? Всего 4 группы пар чисел, в первой группе 19 пар, во второй - 16 пар, в третьей - 21 пара, в четвёртой - 16 пар.

В книге Гарднера "Математические досуги" рассказывается, как У. Адамс строил магический шестиугольник, используя 19 шестиугольных керамических пластинок, складывая из них различные шестиугольники. Он потратил на это занятие 47 лет! Наконец решение получилось, он перерисовал его на бумагу, но она затерялось. В течение последующих пяти лет он безуспешно пытался восстановить решение. В 1962 году бамажка нашлась, и Адамс прислал свой магический шестиугольник Гарднеру.

Вот! А мы тепрь только с компьютером можем строить магические квадраты А компьютер тоже не всегда может.

[Pavlovsky]

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

Для четных порядков число свободных переменных (без учета магической суммы) равно $(N-2)^2$, т.е. 36 для 8-го порядка.Кстати, до сих пор не могу найти простого доказательства этому, хотя с "практической" точки зрения это и очевидно.

У Россера есть лемма 4.2. Количество независимых переменных вычисляется по формуле: $(p)^2- (p-1)r$, где p - порядок квадрата, r - количество наборов путей. Для пандиагонального МК 8х8 получается $(8)^2- (8-1)4=32$

-- Пн сен 20, 2010 09:14:58 --

Упс. Лемма 4.2 верна для простых порядков квадратов. Для пандиагонального МК 8х8 действительно 36 независмых переменных (без учета магической суммы).

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

А ведь про решетку $L(4)$ мы не можем ничего сказать о сумме ее элементов

Кое что сказать можем. У Россера теорема 2.6.


Сумма чисел в ячейках выделенных желтым цветом равна магической сумме.

-- Пн сен 20, 2010 09:24:00 --

[Nataly-Mak]

Дописала в программу третий этап: формирование ещё двух строк. Теперь в программе уже задействовано 17 свободных переменных!

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

11  5  7  263  271  229  269  97 
 41  227  79  199  71  191  193  151 
 257  0  0  0  43  0  0  0 
 239  0  0  0  163  0  0  0 
 23  53  31  179  283  277  293  13 
 211  103  83  149  241  67  197  101 
 233  0  0  0  19  0  0  0 
 137  0  0  0  61  0  0  0

Осталось всего 7 свободных переменных.

Пойду всё-таки завтракать Потом допишу программу до конца.

[Nataly-Mak]

И ещё есть пара столбцов!
Сейчас программа работала 3 секунды. Это невероятно, уже 20 переменных задействовано в программе.

11  5  7  263  271  229  269  97 
 41  251  197  73  71  127  193  199 
 257  191  0  0  139  151  0  0 
 239  173  0  0  67  113  0  0 
 23  53  31  179  283  277  293  13 
 211  167  83  101  241  43  79  227 
 137  149  0  0  19  109  0  0 
 233  163  0  0  61  103  0  0

Осталось совсем чуть-чуть. Ещё один этап, в котором 3 свободных переменных, и последний этап - всего одна переменная.
Прямо с замиранием сердца сейчас запустила программу, никак не ожидала, что опять результат выскочит моментально.

[Nataly-Mak]

Наконец-то заставила программу задуматься

На предпоследнем этапе пришлось разрешить повторение чисел (ждать-то долго не хочется). С таким разрешением программа выполнилась за 3 минуты, вот такой выдала квадрат:

11  5  7  263  271  229  269  97 
 41  251  79  227  83  167  113  191 
 257  211  181  71  37  107  151  137 
 233  173  0  0  151  137  0  0 
 23  53  31  179  283  277  293  13 
 199  127  163  109  241  43  197  73 
 239  193  131  157  19  89  101  223 
 149  139  0  0  67  103  0  0

Ну и остался всего один этап! и только одна свободная переменная.
Сейчас допишу; тоже, конечно, придётся разрешить повторение чисел.
Но главное проверить работу алгоритма до конца.

[svb]

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

У Россера есть лемма 4.2. Количество независимых переменных вычисляется по формуле: $(p)^2- (p-1)r$, где p - порядок квадрата, r - количество наборов путей. Для пандиагонального МК 8х8 получается $(8)^2- (8-1)4=32$

У Россера в лемме 4.1 приводится максимальное число наборов путей $=p+1$, если его поставить в приведенную формулу, то получим число независимых параметров $=p^2-(p-1)(p+1)=1$, т.е. эта формула включает магическую сумму. Если не учитывать этот параметр, то значение формулы нужно уменьшить на 1. Получим для $r=4$ число независимых параметров $=(p-1)(p-3)$. Именно эту формулу для нечетных порядков я раньше приводил. В случае четных порядков число независимых параметров увеличивается на 1 (эффект шахматной доски) и число независимых параметров становится равным $(p-2)^2$. Дополнительным подтверждением сказанного является случай полумагических квадратов. По Россеру получается число независимых параметров $(p-1)^2+1$, а для полумагических квадратов с нулевой суммой имеется очевидный базис из $(p-1)^2$ квадратов-векторов, по которому даже не возникает никаких сомнений и в их независимости и в их полноте.

Цитата:

Кое что сказать можем. У Россера теорема 2.6.

Да, уже посмотрел ...

[Nataly-Mak]

Уф! Программа завершена, результат получен. Но, конечно, это "плохой" квадрат, так как в нём есть одинаковые числа.

11  5  7  263  271  229  269  97 
 41  251  113  227  83  167  79  191 
 257  211  181  71  37  107  151  137 
 233  139  251  43  151  103  53  179 
 23  53  31  179  283  277  293  13 
 199  127  197  109  241  43  163  73 
 239  193  131  157  19  89  101  223 
 149  173  241  103  67  137  43  239

Тем не менее, алгоритм работает. Можно вполне ожидать, что построится и квадрат из различных чисел. Для этого просто надо вставить в программу проверку повторяемости чисел (там, где я её убрала, на последних двух этапах программы) и выполнить программу. Сколько она будет выполняться? Ничего нельзя заранее сказать. Может быть, час, а может быть, 12 часов или и того больше.

Далее необходимо заметить, что программа составлена для одного комплекта отклонений: 6, 12. Но ведь можно брать и другие комплекты. Здесь всё точно так же, как с квадратами 6-го порядка.
Но вот хотя бы для одного комплекта надо как-то выполнить программу. По-моему, отклонения выбраны удачно. Если решение есть, оно должно найтись для таких отклонений.

svb
чтобы выполнить данную программу, я хочу воспользоваться вашим встречным предложением - окомпилировать эту программу вашим супер-быстрым компилятором. Что для этого нужно сделать? Прислать вам исходник программы на Бейсике?

[svb]

Еще немного совершенно простых рассуждений.
$n^2$ - число элементов квадрата.
1. $n$ уравнений для равенства сумм нулю в каждой строке
2. $n-1$ уравнений для равенства сумм нулю в каждом столбце - последний столбец уже не приравниваем 0
3. $n-1$ уравнений для равенства сумм нулю в каждой левой диагонали
4. $n-1$ уравнений для равенства сумм нулю в каждой правой диагонали

Итого $n^2-n-3*(n-1)=(n-1)(n-3)$

Теперь для четных $n$:
1. $n$ уравнений для равенства сумм нулю в каждой строке
2. $n-1$ уравнений для равенства сумм нулю в каждом столбце - последний столбец уже не приравниваем 0
3. $n-1$ уравнений для равенства сумм нулю в каждой левой диагонали
4. $n-2$ уравнений для равенства сумм нулю в каждой правой диагонали. Если раскрасить квадрат как шахматную доску, то после операции 3 нами уже заданы нулевые суммы белых полей и нулевые суммы черных полей, а т.к. диагонали одноцветные, то последнюю белую диагональ не нужно приравнивать нулю, а также последнюю черную.

Итого $n^2-n-2*(n-1)-(n-2)=(n-2)^2$

Nataly-Mak
Присылайте исходник на васике