renuar911's Journal

Красивый способ построения идеального магического квадрата 6 х 6
Москва

Георгий Александров

Идеальные магические квадраты порядка одинарной четности (то есть 6 х 6, 10 х 10 , 14 х 14 и так далее) могут быть только нетрадиционными. То есть они наполняются не последовательным натуральным рядом чисел, а некими выборочными числами. Идеальные квадраты 6-го порядка из произвольных натуральных чисел элементарно получается из квадрата Журбы, который был опубликован в журнале "Наука и жизнь" ещё в прошлом веке. Однако, прямого способа построения я в литературе еще не встречал. Лишь совсем недавно, в сентябре 2013 г. мне удалось найти элегантный графический метод построения. Алгоритм наглядно показан на рисунке

На первом чертеже a) дан прием сортировки чисел для будущего магического квадрата (МК). Строится квадрат последовательных натуральных чисел размером 9 х 9. Число 9 - это полуторная величина от 6. Далее в желтые рамки заключаем те числа, которые нужно изъять из рассмотрения. Оставшиеся числа и присутствуют в чертежах b) - h).
На чертеже b) дан принцип выявления последовательности чисел в самой левой колонке МК сверху вниз. В остальных чертежах - чередование чисел по строкам. Если внимательно присмотреться к чертежам, то можно легко понять единый принцип построения векторов. В результате получим готовый идеальный МК порядка 6 :

Здесь магическая сумма 246. Даже по всем ломаным диагоналям. Кроме того, МК ассоциативный, то есть сумма любых пар центрально противоположных чисел равна 82.

То же самое можно проделать с МК 10 х 10 . Только тут схема отсеивания лишних чисел более интересная и форма графа удивительно красивая:

Магическая сумма 1130 , а центрально противоположные пары чисел дают в сумме число 226 .

Столь строгий и ясный алгоритм позволяет автоматизировать расчеты строить идеальные магические квадраты любого порядка n=4k+2 . Текст программы на языке Yabasic следующий:

rem ПОСТРОЕНИЕ ИДЕАЛЬНОГО МК ПОРЯДКА 4k+2
open #2,"14_MK.txt","w":n=14:nn=2*n:nn2=2*nn
dim z1(nn,nn),z2(nn,nn2),z(nn,nn),a(nn/2),c(900000)
k=n/2:k1=(n-2)/4:x=(n+k+1)/2:n1=n+k:s=n1+1:m=n/2*(n1^2+1)
for i=1 to k1:a(i)=2*i-1:next i:for i=1 to k1+1:a(n/2-i+1)=n1-1-2*(i-1):next i
for i=1 to n/2:z1(i,1)=a(i):next i
for i=n/2+1 to n:z1(i,1)=z1(n-i+1,1):next i
for i=1 to n:z1(i,2)=s-z1(i,1):next i:for k0=1 to n/2-1
for i=1 to n:z1(i,2*k0+1)=z1(i,1):z1(i,2*k0+2)=z1(i,2):next i
next k0:u=0:for i=1 to n:for j=1 to n:z(i,j)=n1*(z1(i,j)-1)+z1(j,i):next j:next i:s0=0
for i=1 to n:s0=0:for j=1 to n:s0=s0+z(i,j):next j:if s0=m then u=u+1:fi:next i:s0=0
for j=1 to n:s0=0:for i=1 to n:s0=s0+z(i,j):next i:if s0=m then u=u+1:fi:next j
for i=1 to n:for j=n+1 to n+n:z(i,j)=z(i,j-n):next j:next i:s0=0:for j=1 to n:s0=0
for i=1 to n:s0=s0+z(i,i+j-1):next i:if s0=m then u=u+1:fi:next j:s0=0:for j=1 to n:s0=0
for i=n to 1 step -1:s0=s0+z(i,i+j-1):next i:if s0=m then u=u+1:fi:next j
if u=4*n then:for i=1 to n*n:c(i)=0:next i:for i= 1 to n:for j=1 to n:z=z(i,j):c(z)=c(z)+1
next j
next i
for i=1 to n:for j=1 to n
print #2,z(i,j) using "###";:next j:print #2:print #2:next i:print #2:fi

Изменяем по надобности лишь два числа, выделенные жирным шрифтом в самом начале программы.
Для наших заданных в тексте параметров получаем идеальный магический квадрат 14 x 14 :

Граф, при помощи которого производится расстановка чисел в первом столбце, очевидно такой:

Метод работает безукоризненно.

Графический подход позволяет не только выявить общее количество идеальных МК, но и выбрать самый оптимальный. Для сравнения привожу МК 14 х 14 , построенный Н.Макаровой и найденный графически:

Четно-нечетный узор в моем варианте более укрупненный, что говорит о лучшей стройности расстановки чисел. Данный аспект легко доказывается на примере построения самой левой колонки. У Макаровой граф получается бессистемный: он как заяц скачет по кочкам

В моем случае граф более последовательный: стрелки сначала спускаются вниз, затем вверх

Из данных двух примеров хорошо видно, что можно сосчитать возможное количество графов комбинаторным способом. То есть можно выявить число идеальных магических квадратов.

Такой же метод можно применить и для построения идеальных магических квадратов порядка двойной четности ( n=8, 12, 16, 20, ... ). Покажем подробно, как построить ИМК 12 х 12. Строим матрицу последовательных натуральных чисел:

Теперь рассмотрим левую и правую колонки. Вычисляем суммы пар чисел (жирные черные цифры)

Выделяем в желтых рамках те числа, которые дают магическую сумму S= 13+61+157+181+205+253=870 . Причем числа так должны быть расположены, чтобы красные числа (те же черные, но в обратном порядке) оказались в строках, где черные числа не обведены желтыми рамками. Теперь можно строить граф:

Получили в итоге первую колонку будущего магического квадрата. Построив подобным образом еще 12 графов (как это было сделано в самом первом примере данной лекции) в итоге рисуем окончательное решение:

Точно так же построен такой квадрат:

Приведу еще квадрат шестнадцатого порядка:

Обратите внимание на слоистую структуру четно-нечетного рисунка последних трех квадратов. Это говорит о строго едином методе их построения.

В заключение хочу озвучить следующую важную мысль: графический метод лучше остальных вскрывает суть задачи построения идеальных магических квадратов. Например, если рассматривать МК нечетного порядка, то вместо многостраничных рассуждениях о латинских квадратах, всяких "качелях" и ходах конем, достаточно просто в поле повторяющихся натуральных рядов чисел выделить кружками сначала главную диагональ, а затем и остальные элементы. Образуется четкая решетка, в узлах которых - идеальный магический квадрат. Так, для МК порядка n=5 будем иметь:

Более компактный способ получения того же идеального квадрата следующий:

Правда, есть одно "но". Этот метод действует, если порядок магического квадрата не кратен трем. Для n = 9 , 15, 21 и так далее разработан более сложный метод.
Метод этот базируется на цепях Александрова.
Приведу несколько цепей Александрова для МК 9 х 9, 15 х 15, 21 х 21 и т. д. :

1 9 3 6 2 5 8 4 7

1 15 3 6 2 5 7 4 8 12 9 11 14 10 13

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

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

1 33 3 6 2 5 7 4 8 12 9 11 13 10 14 18 15 17 19 16 20 24 21 23 25 22 26 30 27 29 32 28 31

1 39 3 6 2 5 7 4 8 12 9 11 13 10 14 18 15 17 19 16 20 24 21 23 25 22 26 30 27 29 31 28 32 36 33 35 38 34 37

1 45 3 6 2 5 7 4 8 12 9 11 13 10 14 18 15 17 19 16 20 24 21 23 25 22 26 30 27 29 31 28 32 36 33 35 37 34 38 42 39 41 44 40 43

Подробнее:
http://renuar911.narod.ru/IMS_Alexandrov.html

Теорию получения цепей Александрова смотрите в
http://renuar911.narod.ru/IMSb.html

Методом цепей Александрова можно построить идеальные магические квадраты нечетного порядка ( причем все, за исключением 3 х 3 ) при помощи программы на Yabasic

rem Программа построения идеальных магических квадратов методом Г.М.Александрова
open #1,"IMS_Alex.txt","w"
dim p(1000000),t(50000),r(50000),z(4200,4200)
print "INPUT ORDER OF IMS n ";:input n
if int(n/2)=n/2 then print "Order n is EVEN! YOU MUST INPUT ONLY UNEVEN n ! "
end:fi
n1=(n-3)/2
p(1)=1:p(2)=n:p((1+n)/2+1)=(1+n)/2:no=(n-3)/2
t(5)=3:t(7)=6:t(9)=2
if n<5 then print "Order n < 5 and NO IMS":fi
if n=5 then p(3)=2:p(n)=4
Print #1,"Цепь Александрова":print #1
for i=1 to n:print p(i);:print #1,p(i);:next i:print:print #1
print #1, "____________________________________________________"
print #1:fi
if n=7 then p(3)=3:p(4)=6:p(6)=2:p(n)=5
print #1,"Цепь Александрова":print #1
for i=1 to n:print p(i);:print #1,p(i);:next i:print:print #1
print #1, "____________________________________________________"
print #1:fi
if n=9 then p(3)=3:p(4)=6:p(5)=2:p(7)=8:p(8)=4:p(n)=7
print #1,"Цепь Александрова":print #1
for i=1 to n:print p(i);:print #1,p(i);:next i:print:print #1
print #1, "____________________________________________________"
print #1:fi
if n>9 then
t(11)=5:t(13)=7:t(15)=4:t(17)=8:t(19)=12:t(21)=9
s=21
for k=1 to (n+1)/2:for i=1 to 6:s=s+2:t(s)=6*k+t(9+2*i):next i:next k
rem Блок корректировки значений t(i)
o=mod(n,12)
if o=11 then t(n-4)=t(n-4)-2:fi
if o=1 or o=7 then t(n)=t(n)-3:fi
s1=2:s0=0
Print #1,"Цепь Александрова":print #1
for i=5 to n step 2:s1=s1+1:p(s1)=t(i):s0=s0+1:r(s0)=1+n-t(i):next i
s1=s1+1
for i=n to 5 step -2:s1=s1+1:p(s1)=r(s0):s0=s0-1:next i
for i=1 to n:print p(i);:print #1,p(i);:next i: print:print #1
print #1, "_____________________________________________________"
print #1
print #1:print #1,"ИДЕАЛЬНЫЙ МАГИЧЕСКИЙ КВАДРАТ ПОРЯДКА ";:print #1,n
print #1:fi
s=0:s1=0:s0=0
rem Построение идеального магического квадрата
for k=1 to n:for t=1 to n
if k=1 and t=1 then j=(n+1)/2:i=(n+1)/2-1:fi
if t=1 and k>1 then i=i+2:if j<0 then j=j+n:fi:if i<0 then i=i+n:fi:fi
if t>1 then i=i+1:j=j+2:fi
rem приведение i и j к рамкам магического квадрата
v=i
a()
i=v2:v=j
a()
j=v2:z=(p(k)-1)*n+p(t):z1=int(z)
if abs(z-z1)>.9 then z=z1+1 else z=z1:fi
z(i,j)=z:next t:next k
rem Печать идеального магического квадрата
print #1
for i=1 to n:for j=1 to n
print #1,z(i,j) using "####";:next j
print #1:print #1:next i

sub a()
v0=v/n:v1=int(v0):if v0<1 then v1=0:fi
v2=(v0-v1)*n:v3=int(v2)
if abs(v2-v3)>.9 then v2=v3+1 else z=v3:fi
if abs(v2)<.0000000001 then v2=n:fi
end sub

Чтобы понять принцип построения, рассмотрим пример. Пусть требуется построить идеальный магический квадрат 15 x 15. Цепь Александрова для него:
1 15 3 6 2 5 7 4 8 12 9 11 14 10 13

Строим вспомогательный рисунок:

Вверху и слева пишем цепь Александрова а значения Z внутри квадрата вычисляем по формуле, что над рисунком.
Например, в желтой ячейке число 111 вычисляется так: 15(8 - 1) + 6
Далее начинаем заполнять идеальный МК. Первое число 1 помещаем прямо над центром всего квадрата. Затем ходом шахматного коня проставляем числа первой строки предыдущего квадрата. После последней цифры 13 следует опуститься через ячейку и с зеленой ячейки начать ходом коня проставлять числа второй строки предыдущего квадрата.

В результате получим идеальный магический квадрат:

Программа позволяет выдавать этим же способом любые ИМК нечетного порядка. Например, идеальный магический квадрат 5 x 5 будет построен так:

Итак, эта лекция фактически есть венец моих многолетних исследований, закончившихся поиском не просто магических, а самых магических квадратов. То есть идеальных магических квадратов. Причем, среди множества ИМК найдены наиболее красивые.

Доклад прочитан на конференции Национального университета Ла-Платы
(Universidad Nacional de La Plata, UNLP)
2013 г.