renuar911's Journal

Глава 36. Мы продолжаем искать самые идеальные магические квадраты
- Деда, деда, вставай! Уже девять часов, посмотри, какой туман! Дом напротив почти не виден.
- Туман, говоришь? А ты знаешь, что такое туман?
- Знаю, знаю. Это облако, которое спустилось на землю. Ты сам говорил.
- Верно! А я и не помню, чтобы такое тебе говорил... Ладно, встаем, пьем чай и делаем зарядку. То есть, наоборот,- делаем зарядку, закаляемся, чистим зубки и завтракаем.
- Давай, дедуля! Хватит дрыхнуть!
- Все, все, встаю, Андрюшенька. Вот ведь какой ты настырный. Как сибиряк...

- Андрюша! Итак, мы позавтракали, гулять пойдем после обеда. Надеюсь, что туманное облако поднимется и дождя не будет. Сейчас давай попишем прописи и порисуем.
- А потом?
- А потом продолжим искать идеальные магические квадраты.
- Годится! Какие буквы писать? Ах, да, - в прописях образцы даны. Я сегодня должен заполнить три страницы.
- Лучше четыре. Четверка же лучше тройки...

- Все, дедуль! Теперь нарисую картину. Ты акварельные краски достал?
- Так вот коробка, перед самым твоим носом.
- Гы-гы. Перед носом. Сегодня я буду рисовать дом напротив. Едва-едва различимый. А как нарисовать туман?...

- Все! Готово! Пойду покажу маме. А ты приготовь что надо по магическим квадратам...
- Ну, как? Мама оценила твое художество?
- Оценила! Сказала только, что антенны на крыше слишком жирные.
- Замечание верное. Но видишь, какая у тебя кисточка? Ей только заборы красить. Разве тонкие линии сделаешь?
- Все, дедуль. Теперь займемся делом. Итак, у нас на очереди четные квадраты?
- Начнем. Прежде тебе напомню вот что. Идеальные магические квадраты, или ИМК, нечетного порядка, как ты помнишь, разбивались на две группы: кратные тройке и остальные, то есть у которых n не делится на три. Для каждого случая мы нашли несколько методов построения. Теперь ИМК четного порядка. Тут тоже два вида: первый - одинарной четности и второй - двойной четности.
- А, помню! Одинарная четность - это нечетное число, умноженное на два. Это числа 6, 10, 14, 18 и так далее. Двойная же четность - это числа 4, 8, 12, 16 и так далее.
- Верно, Андрюшенька! Тогда начинаем с первого. Идеальные магические квадраты порядка одинарной четности (то есть 6 х 6, 10 х 10 , 14 х 14 и так далее) могут быть только нетрадиционными. То есть они наполняются не последовательным натуральным рядом чисел, а некими выборочными числами.
- И как выбирать такие числа?
- Я нашел простой способ отсеивания лишних чисел. Допустим, мы хотим создать идеальный магический квадрат 6 x 6. Однажды я подумал: а что если последовательный натуральный ряд чисел записать в матрице 7 x 7 и затем выделить центральные строку и колонку.
- А, понял! И затем числа в них просто удалить, да?
- Верно, Андрюшенька. И у нас получится укороченная матрица 6 x 6. Вот смотри на этом слайде:

- То есть мы как бы ужали на одну строку и один столбец? А что это за синие числа справа?
- Это просто суммы крайних пар чисел: 1+7=8 ; 8+14=22 и так далее.
- Зачем же они нам нужны?
- Вот тут, дорогой мой, - самое интересное. Но прежде чем продолжить, нам следует найти магическую сумму. Ее получим, если рассмотрим числа главной диагонали:

S = 1 + 9 + 17 + 33 + 41 + 49 = 150

- Забавно! Насколько я помню, магическая сумма обычного магического квадрата равна 111 .
- Верно. Но это у обыкновенного магического квадрата. А у нас он будет нетрадиционным. Итак, мое маленькое открытие такое: нужно попытаться найти такие три разные синие числа, чтобы сумма их была точно 150 . Причем число 8 должно присутствовать обязательно.
- Это почему, дедуль?
- Вот почему: мы будем искать идеальный магический квадрат, у которого единичка будет находиться в левом верхнем углу. То есть в первой строке.
- Тогда получается, что нужно найти только два синих числа?
- Да, ты прав. Задача немного упрощается.
- Погоди, погоди! Я не понял, почему вообще именно три числа участвуют в сумме?
- Это просто. Каждое синее число - это сумма двух чисел в матрице. То есть мы имеем дело уже с шестью числами. Что логично: ведь ищем же идеальный квадрат шестого порядка!
- Ясно теперь. Но давай я попробую найти два синих числа. Допустим одно из них будет 78 и тогда

150-8-78=64

и такое число у нас есть! Смотри, дедуля!
- Да не кричи ты так. Соседей разбудишь. Но ты ловко решил задачу! Поздравляю! Но самое трудное впереди. И попытайся понять. Пусть наши найденные три числа будут обозначены как черные квадратики. А остальные - как маленькие звездочки. Пишем числа сначала слева направо, а точно под этим - справа налево. Вот так:

Мы с тобой видим, что ни в одном месте нет такого, чтобы под черным квадратом был тоже черный квадрат. У нас, значит все нормально и идеальный магический квадрат построить можно.
- А бывают случаи, что нельзя?
- Конечно! Если ты то же самое сделаешь с исходной матрицей 10 х 10 , то подобного благополучия не увидишь. Можешь на досуге проверить.
- А что тогда придется делать?
- Тогда придется не одну строку и один столбец убирать, а по нескольку. Но об этом потом скажу. Так вот, следующий шаг уже графический и тоже интересный. Нужно построить все возможные графы такого вида:

- Деда, а что так мало? Я бы мог десятки вариантов найти.
- Попробуй! Но имей в виду, что граф должен быть симметричным относительно срединной вертикали и линии всегда идут то направо, то налево.
- Да, дедуль, я поиграл то направо, то налево, - все остальные варианты несимметричные относительно вертикали. А какую среди двух выбирать?
- Сделаем подробно первый граф, а потом видно будет. Этот первый граф даст нам первую колонку будущего идеального магического квадрата. Вот так:

Ты хорошо понял, как все получается?
-Да, дедуль. По стрелочкам идем и пишем нужные цифры. Все пока ясно.
- Вот и ладушки. Теперь заполняем строки. Та же самая система, но уже по горизонтали. Смотри внимательно - первая строка:

- Так, дедуль, погоди. Все ясно! Та же система графа, отлично!
- Теперь вторая строка:

Третья строка:

Четвертая строка:

Пятая строка:

Ну, и последняя шестая строка:

В итоге получен идеальный магический квадрат. Я уверен в этом на сто процентов, хотя еще не проверял. Проверь уж ты, будь добр.
- Проверю, дедуль. Только не уходи, я быстро... Так, действительно все идеально! Ну и метод! Буквально можно на пальцах получить результат. Главное, что все логично, а вычислений минимум.
- Ах, да! Я забыл про второй граф. Вот что, я дам только рисунок для построения первой колонки и рядом окончательный идеальный магический квадрат. Хорошо?
- Хорошо, дедуль!
- Тогда поехали:

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

Итак, магическая сумма, как ты говорил, равна 111 . Делаем простые вычисления:

111 - 7 - 19 = 85
111 - 7 - 31 = 73
111 - 7 - 43 = 61
111 - 7 - 55 = 49
111 - 7 - 67 = 37

Так, так... Как видим, перебрали все варианты, а подобрать нужную сумму невозможно. Видимо, тут ответ на твой вопрос.
Конечно, я на досуге проверю другие размеры квадратов. Вот ведь как интересно оказалось!
- Да, дедуля! Таких доказательств история еще не знала.
- Не знаю, не знаю... Возможно, мы с тобой не нашли еще книги какого-нибудь восемнадцатого века. Но в интернете такого точно нет и это успокаивает. Но скоро обед, надо двигаться дальше. А дальше вот что. Мы с тобой нашли идеальный магический квадрат, когда убрали одну строку и одну колонку. Однако, я доказал в одной из своих статей, что это не есть универсальное действие. Универсальное действие - это убрать 0.5 n строк и 0.5 n столбцов. Здесь n порядок идеального магического квадрата. Причем, в определенных местах матрицы размером 1.5 n х 1.5 n . То есть для нашего с тобой предыдущего варианта нужно построить матрицу 9 х 9 и убрать три строки и три столбца. Эту задачу я успешно решил и покажу решение на слайдах:

На первом чертеже 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 графов (как это было сделано в самом первом примере данной лекции) в итоге рисуем окончательное решение:

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

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

Обрати внимание на слоистую структуру четно-нечетного рисунка последних трех квадратов. Это говорит о строго едином методе их построения.
- Удивил ты меня, дедуля! Прямо профессором стал государственного университета.
- Вся математика - вещь удивительная. Куда ни копнешь - только вздыхай и изумляйся. Все наши главы книги - тому яркие подтверждения.

Москва
22 ноября 2013 г.