Магічний квадрат

Магічний квадрат — це квадратна таблиця $n\times n$, заповнена $n^{2}$ числами таким чином, що сума чисел у кожному рядку, кожному стовпчику і на обох діагоналях однакова. Якщо в квадраті рівні суми чисел тільки в рядках і стовпцях, то він називається напівмагічним. Нормальним називається магічний квадрат, заповнений цілими числами від $1$ до $n^{2}$. Магічний квадрат називається асоціативним або симетричним, якщо сума будь-яких двох чисел, розташованих симетрично щодо центру квадрата, дорівнює $n^{2}+1$.

Нормальні магічні квадрати існують для всіх порядків $n\geq 1$, за винятком $n=2$, хоча випадок $n=1$ тривіальний — квадрат складається з одного числа. Мінімальний нетривіальний випадок показаний нижче, він має порядок 3.

		2	7	6	$\rightarrow$	15
		9	5	1	$\rightarrow$	15
		4	3	8	$\rightarrow$	15
	$\swarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\searrow$
15		15	15	15		15

Сума чисел в кожному рядку, стовпчику і по діагоналях, називається магічною сталою, M. Магічна константа нормального магічного квадрата залежить тільки від n і визначається формулою:

$M(n)={\frac {n(n^{2}+1)}{2}}$

Перші значення магічних констант наведені в наступній таблиці (послідовність A006003 з Онлайн енциклопедії послідовностей цілих чисел, OEIS):

Порядок n	3	4	5	6	7	8	9	10	11	12	13
Mn	15	34	65	111	175	260	369	505	671	870	1105

Історія

Квадрат Ло шу (Китай)

4 9 2 3 5 7 8 1 6

Ло шу (кит. | 洛書 | 洛书 | luò shū) Єдиний нормальний магічний квадрат 3 × 3. Був відомий ще в Стародавньому Китаї, перше зображення на черепаховому панцирі датується 2200 роком до н. е..

Квадрат, знайдений в Кхаджурахо (Індія)

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

Це найраніший з виявлених унікальний магічний квадрат, що був знайдений в написі XI століття в індійському місті Кхаджурахо. Це перший магічний квадрат, що відноситься до різновиду так званих «диявольських» квадратів.

Магічний квадрат Ян Хуея (Китай)

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

У 13 ст. математик Ян Хуей зайнявся проблемою методів побудови магічних квадратів. Його дослідження були потім продовжені іншими китайськими математиками. Ян Хуей розглядав магічні квадрати не тільки третього, а й більших порядків. Деякі з його квадратів були достатньо складні, однак він завжди давав правила для їх побудови. Він зумів побудувати магічний квадрат шостого порядку, причому останній виявився майже асоціативним (у ньому тільки дві пари центрально протилежних чисел, що виділені жирним шрифтом, не дають суму 37).

Квадрат Альбрехта Дюрера

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

Магічний квадрат 4 × 4, зображений на гравюрі Альбрехта Дюрера «Меланхолія I», вважається найбільш раннім в європейському мистецтві. Два середні числа в нижньому ряду вказують дату створення картини (1514, в таблиці виділено жирним). Сума чисел на будь-який горизонталі, вертикалі і діагоналі дорівнює 34. Ця сума також зустрічається в усіх кутових квадратах 2 × 2, в центральному квадраті (10 + 11 + 6 + 7), у квадраті з кутових клітин (16 + 13 + 4 + 1), в рядах чисел, побудованих «ходом коня» ((2 + 8 + 9 + 15) і (3 + 5 + 12 + 14)), прямокутниках, утворених парами середніх клітин на протилежних сторонах ((3 + 2 + 15 + 14) і (5 + 8 + 9 + 12)). Більшість додаткових симетрій пов'язано із тим, що сума будь-яких двох центрально симетрично розташованих чисел дорівнює 17.

Квадрати Генрі Дьюдені та Аллана Джонсона-молодшого

67 1 43 13 37 61 31 73 7

3 61 19 37 43 31 5 41 7 11 73 29 67 17 23 13

Якщо в квадратну матрицю n × n заноситься не строго натуральний ряд чисел, то цей магічний квадрат — нетрадиційний. Поряд представлені два такі магічні квадрати, заповнені в основному простими числами. Перший (має порядок n = 3) — квадрат Дьюдені, в якому сума чисел будь-якого рядка = 111; другий (має порядок n = 4) — квадрат Джонсона, в якому сума чисел будь-якого рядка = 120. Обидва вони були розроблені на початку двадцятого століття.

Наступний квадрат, побудований в 1913 році Дж. Н. Мансі, примітний тим, що він складений з 143 послідовних простих чисел за винятком двох моментів: залучена одиниця, яка не є простим числом, і не використано єдине парне просте число — 2.

1	823	821	809	811	797	19	29	313	31	23	37
89	83	211	79	641	631	619	709	617	53	43	739
97	227	103	107	193	557	719	727	607	139	757	281
223	653	499	197	109	113	563	479	173	761	587	157
367	379	521	383	241	467	257	263	269	167	601	599
349	359	353	647	389	331	317	311	409	307	293	449
503	523	233	337	547	397	421	17	401	271	431	433
229	491	373	487	461	251	443	463	137	439	457	283
509	199	73	541	347	191	181	569	577	571	163	593
661	101	643	239	691	701	127	131	179	613	277	151
659	673	677	683	71	67	61	47	59	743	733	41
827	3	7	5	13	11	787	769	773	419	149	751

Види магічних квадратів

• Нормальний (англ. normal) — магічний квадрат, заповнений цілими числами від $1$ до $n^{2}$.
• Напівмагічний (англ. semimagic) — магічний квадрат, заповнений числами від $1$ до $n^{2}$, причому сума чисел по горизонталях і вертикалях дорівнює магічній константі, а по діагоналях ця умова не виконується.
• Асоціативний (англ. associative), або симетричний  — магічний квадрат, у якого сума будь-яких двох чисел, що розташовані симетрично відносно центра квадрата, дорівнює одному й тому ж числу: $1+n^{2}$.
• Пандіагональний (англ. pandiagonal), або диявольський (англ. satanic) — магічний квадрат, в якого сума чисел по ламаних діагоналях також дорівнює магічній константі.
• Ідеальний (англ. ultra magic) — магічний квадрат, що одночасно є пандіагональним і асоціативним.
• Досконалий (англ. most-perfect) — магічний квадрат четвертого порядку, що є пандіагональним та має ряд додаткових властивостей.^[яких?] Всі магічні квадрати 4 порядку є досконалими.
• Бімагічний (англ. bimagic) — магічний квадрат, що залишається магічним після заміни всіх його елементів на їх квадрати. Бімагічних квадрати 3, 4 і 5 порядків не існує.
• Мультимагічний (англ. multimagic) — узагальнення властивостей бімагічних квадратів на довільний степінь $n$.
• Квадрати Б. Франкліна (англ. Franklin) — магічні квадрати, які крім основних властивостей мають додаткові унікальні особливості.

Побудова магічних квадратів

Способи побудови магічних квадратів поділяються на три категорії в залежності від того, магічний квадрат якого порядку ви хочете побудувати:

• непарний;
• дорівнює непарному числу, помноженому на 2;
• дорівнює натуральному числу, помноженому на 4.

Загальний метод побудови магічних квадратів всіх типів невідомий, а можливо і не існує, хоча широко застосовуються різні спеціалізовані алгоритми. Знайти всі магічні квадрати порядку n вдається тільки для $n\leq 4$, тому становлять великий інтерес способи побудови магічних квадратів при $n>4$. Найпростішим є алгоритм побудови магічного квадрата непарного порядку. Якщо присвоїти клітинкам квадрата координати, наприклад $(i,j)$, то значення числа в клітинці можна розрахувати за формулою $1+((i-j+(n-1)/2){\bmod {n}})n+((i+j+(n+1)/2){\bmod {n}})$.

Також розроблені алгоритми побудови пандіагональних квадратів, та ідеальних магічних квадратів 9 порядку. Ці результати дозволяють будувати ідеальні магічні квадрати порядків $n=9(2k+1)$. Існують також загальні методи компонування ідеальних магічних квадратів непарного порядку $n>3$. Розроблено методи побудови ідеальних магічних квадратів порядку $n=8k$, де $K=1,2,3...$, і досконалих магічних квадратів. Пандіагональні та ідеальні квадрати парного-непарного порядку вдається скомпонувати лише в тому випадку, якщо вони нетрадиційні. Тим не менш, можна знаходити майже пандіагональні квадрати. Знайдена особлива група ідеально-досконалих магічних квадратів (традиційних і нетрадиційних).

Метод побудови магічного квадрата непарного порядку

Описаний французьким дипломатом de la Loubère у його книзі «A new historical relation of the kingdom of Siam»

Побудова починається з центральної клітинки верхнього ряду, куди ми вписуємо 1. Надалі ми будемо рухатися на одну клітинку вгору і вправо за один крок вписуючи послідовний ряд чисел від $1$ до $n^{2}$. Якщо ми дійшли до правого стовпця чи верхнього рядка, то з наступним кроком пересуваємось до протилежного лівого чи нижнього краю відповідно. Якщо наступна клітинка вже зайнята, то просто рухаємось на 1 клітинку вниз. Продовжуємо виконувати ці кроки $n^{2}$ разів, доки не заповнимо всі клітинки.

крок 1 1 . .

крок 2 1 . 2

крок 3 1 3 2

крок 4 1 3 4 2

крок 5 1 3 5 4 2

крок 6 1 6 3 5 4 2

крок 7 1 6 3 5 7 4 2

крок 8 8 1 6 3 5 7 4 2

крок 9 8 1 6 3 5 7 4 9 2

Можна починати будувати магічний квадрат і з інших клітин верхнього ряду, проте тоді сумма діагоналей не буде рівною магічній константі(отримаємо напівмагічний квадрат). В процесі побудови можна вибрати й інший напрям руху(вгору і вліво, вниз і вліво, вниз і вправо). Як результат знову отримаємо справжній магічний квадрат.

Метод терас

Описаний Ю. В. Чебраковим у «Теорії магічних матриць».

Для заданого непарного $n$ накреслимо квадратну таблицю розміром $n\times n$. Добудуємо до цієї таблиці з усіх чотирьох сторін тераси (пірамідки). В результаті отримаємо ступінчасту симетричну фігуру. Починаючи з лівої вершини ступінчастої фігури, заповнимо її діагональні ряди послідовними натуральними числами від $1$ до $n^{2}$.

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

Після цього для отримання класичної матриці порядку n, що знаходяться в терасах, поставимо на ті місця таблиці розміром $n\times n$, в яких вони були б, якщо переміщати їх разом з терасами до того моменту, поки підстави терас не долучаться до протилежної сторони таблиці.

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

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

Приклади програмної реалізації алгоритмів побудови магічних квадратів

Побудова

Метод терас (квадрати непарного порядку). Реалізація на мові програмування Python 3:

from collections import defaultdict

def recursive_defaultdict():
    return defaultdict(recursive_defaultdict)

def create_magic_square(N):
    assert(N % 2 == 1)
    arr = recursive_defaultdict()

    # Створення ступінчастої симетричної фігури
    num = 1
    ii = (N + 1) // 2
    jj = 2 - ii
    while num < N**2:
        i, j = ii, jj
        while i + 1 != jj:
            arr[i][j] = num
            i, j, num = i-1, j+1, num+1
        ii, jj = ii+1, jj+1

    # Заповнення лівої частини квадрата, щодо 
    # лівої діагоналі (саму діагональ не чіпаємо) 
    ii, jj = 1, N
    while ii < N and jj > 1:
        for j in range(1, jj+1):
            if ii not in arr or j not in arr[ii]:
                if ii + N in arr and j in arr[ii + N]:
                    arr[ii][j] = arr[ii+N][j]
                else:
                    arr[ii][j] = arr[ii][j+N]
        ii, jj = ii+1, jj-1

    # Заповнення правої частини квадрата, щодо 
    # лівої діагоналі (саму діагональ не чіпаємо) 
    jj = N - 2
    for i in range(N, 1, -1):
        for j in range(N, N-jj-1, -1):
            if i not in arr or j not in arr[i]:
                if i-N in arr and j in arr[i-N]:
                    arr[i][j] = arr[i-N][j]
                else:
                    arr[i][j] = arr[i][j-N]
        jj -= 1

    # Конвертуємо з асоціативного у лінійний масив
    square = [[arr[i][j] for j in range(1,N+1)] for i in range(1,N+1)]
    return square

Джерела

Я. В. Успенский, «Избранные математические развлечения»
Н. М. Рудин, «От магического квадрата к шахматам»
Б. А. Кордемский, «Математическая смекалка»
Е. Я. Гуревич, «Тайна древнего талисмана»
М. М. Постников, «Магические квадраты»

Посилання

• Магические квадраты^{[недоступне посилання з листопадаа 2019]}(англ.)
• Н.Макарова
  • «Волшебный мир магических квадратов»
  • «Магические квадраты: основные понятия; построение с помощью компьютера»
  • «Методы построения магических квадратов»
  • «Построение магических квадратов чётно-нечётного порядка методом четырёх квадратов»
  • «Пандиагональные магические квадраты»
  • «Полумагические квадраты»
  • «Пандиагональные квадраты пятого порядка»
  • «Базовые пандиагональные квадраты пятого порядка»
  • «Ассоциативные магические квадраты»
  • «Магические квадраты седьмого порядка»
  • «Магические квадраты восьмого порядка»
  • «Магические квадраты одиннадцатого порядка»
  • «Магические квадраты двенадцатого порядка»
  • «Магические квадраты пятнадцатого порядка»
  • «Пандиагональные квадраты чётно-чётных порядков»
  • «Метод качелей для пандиагональных квадратов чётно-чётного порядка. [Архівовано 14 квітня 2011 у Wayback Machine.]»
  • «Квадраты Франклина. [Архівовано 20 січня 2010 у Wayback Machine.]»
  • «Разработка древнего алгоритма. [Архівовано 28 квітня 2011 у Wayback Machine.]»
  • «Метод построения идеальных магических квадратов порядка n=k^p. [Архівовано 27 квітня 2011 у Wayback Machine.]»
  • «Полные комплекты квадратов Франклина.»
  • «Новые аспекты метода латинских квадратов.»
  • «Наименьшие магические квадраты из простых чисел. [Архівовано 29 червня 2010 у Wayback Machine.]»
• послідовність A164843 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
  • «Общие формулы магических квадратов.»
• Магический квадрат - иллюзия предугадывания
• М.Гарднер «Рецензия на книгу Кэтлин Оллереншоу и Дэвида Бри [Архівовано 16 лютого 2018 у Wayback Machine.]»
• H.Heinz Magic Squares, Magic Stars & Other Patterns(англ.)
• Н.Скрябина, В.Дубовской Магические квадраты [Архівовано 28 квітня 2011 у Wayback Machine.]
• Шахматный подход [Архівовано 1 грудня 2008 у Wayback Machine.]
• Цепи Александрова
• Цепи Александрова. Аналитические выражения^{[недоступне посилання з липня 2019]}
• Г.Александров
  • «Магия чисел и слов (Монография, 266 с.)»^{[недоступне посилання з листопадаа 2019]}
  • «Магические квадраты регулярного вида [Архівовано 5 березня 2016 у Wayback Machine.]»
  • «Идеальные магические квадраты 8х8 и 12х12 [Архівовано 4 березня 2016 у Wayback Machine.]»
  • «Идеальные магические квадраты 20х20,28x28,36х36 [Архівовано 4 березня 2016 у Wayback Machine.]»
  • «Идеальный магический квадрат порядка 8k. Самый простой метод построения [Архівовано 5 березня 2016 у Wayback Machine.]»
  • «Идеальные магические квадраты порядка 4k [Архівовано 5 березня 2016 у Wayback Machine.]»
  • «Идеальные магические квадраты [Архівовано 3 грудня 2012 у Wayback Machine.]»
  • «Построение идеального магического квадрата из двух латинских квадратов [Архівовано 10 жовтня 2017 у Wayback Machine.]»
  • «Идеальные магические квадраты, приведенные к единому началу [Архівовано 4 березня 2016 у Wayback Machine.]»
  • «Красивый способ построения магических квадратов [Архівовано 30 серпня 2016 у Wayback Machine.]»