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

Історія

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

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

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

Джерела

Посилання

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

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

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

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

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

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

Метод терас

Побудова

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

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

Сума чисел в кожному рядку, стовпчику і по діагоналях, називається магічною сталою, 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}$ , причому сума чисел по горизонталях і вертикалях дорівнює магічній константі, а по діагоналях ця умова не виконується.
Асоціативний (рос. ассоциативный, англ. mystic), або симетричний (рос. симетричный) — магічний квадрат, у якого сума будь-яких двох чисел, що розташовані симетрично відносно центра квадрата, дорівнює одному й тому ж числу: $1+n^{2}$ .
Пандіагональний (рос. пандиагональный, англ. Multimagic), або диявольський (рос. диявольский, англ. Satanic) — магічний квадрат, в якого сума чисел по ламаних діагоналях також дорівнює магічній константі.
Ідеальний (рос. идеальный, англ.) — магічний квадрат, що одночасно є пандіагональним і асоціативним.
Досконалий (рос. совершенный, англ.) — магічний квадрат четвертого порядку, що є пандіагональним та має ряд додаткових властивостей. Всі магічні квадрати 4 порядку є досконалими.
Бімагічний (рос. бимагический, англ. bimagic) — магічний квадрат, що залишається магічним після заміни всіх його елементів на їх квадрати. Бімагічних квадрати 3, 4 і 5 порядків не існує.
Мультимагічний (рос. мультимагический, англ. multimagic) — узагальнення властивостей бімагічних квадратів на довільний степінь $n$ .
Квадрати Б. Франкліна (рос. квадраты Б. Франклина) — магічні квадрати, які крім основних властивостей мають додаткові унікальні особливості.

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

непарний;
дорівнює непарному числу, помноженому на 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

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

$\rightarrow$

$\rightarrow$

$\rightarrow$

$\swarrow$

$\downarrow$

$\downarrow$

$\downarrow$

$\searrow$

Магические квадраты^{[недоступне посилання з листопадаа 2019]}(англ.)
Н.Макарова
послідовність A164843 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- «Общие формулы магических квадратов.»
Магический квадрат - иллюзия предугадывания
М.Гарднер «Рецензия на книгу Кэтлин Оллереншоу и Дэвида Бри»
H.Heinz Magic Squares, Magic Stars & Other Patterns(англ.)
Н.Скрябина, В.Дубовской Магические квадраты
Шахматный подход
Цепи Александрова
Цепи Александрова. Аналитические выражения^{[недоступне посилання з липня 2019]}
Г.Александров

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.