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

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

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

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

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

${\displaystyle 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) — магічний квадрат, заповнений цілими числами від ${\displaystyle 1}$ до ${\displaystyle n^{2}}$.
• (англ. semimagic) — магічний квадрат, заповнений числами від ${\displaystyle 1}$ до ${\displaystyle n^{2}}$, причому сума чисел по горизонталях і вертикалях дорівнює магічній константі, а по діагоналях ця умова не виконується.
• (англ. associative), або симетричний  — магічний квадрат, у якого сума будь-яких двох чисел, що розташовані симетрично відносно центра квадрата, дорівнює одному й тому ж числу: ${\displaystyle 1+n^{2}}$.
• (англ. pandiagonal), або диявольський (англ. satanic) — магічний квадрат, в якого сума чисел по ламаних діагоналях також дорівнює магічній константі.
• (англ. ultra magic) — магічний квадрат, що одночасно є пандіагональним і асоціативним.
• (англ. most-perfect) — магічний квадрат четвертого порядку, що є пандіагональним та має ряд додаткових властивостей.^[] Всі магічні квадрати 4 порядку є досконалими.
• (англ. bimagic) — магічний квадрат, що залишається магічним після заміни всіх його елементів на їх квадрати. Бімагічних квадрати 3, 4 і 5 порядків не існує.
• (англ. multimagic) — узагальнення властивостей бімагічних квадратів на довільний степінь ${\displaystyle n}$.
• (англ. Franklin) — магічні квадрати, які крім основних властивостей мають додаткові унікальні особливості.

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

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

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

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

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

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

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

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

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

Метод терас

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

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

${\displaystyle 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 . ${\displaystyle X}$ -4 -3 -2 -1 0 1 2 3 4

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

${\displaystyle 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 . ${\displaystyle 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 (англ.)
• Н.Скрябина, В.Дубовской Магические квадраты [ 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.]»