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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Напівмагічний квадрат)
Перейти до навігації Перейти до пошуку

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

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

2 7 6 15
9 5 1 15
4 3 8 15
15 15 15 15 15

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


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

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

[ред. | ред. код]

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

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

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

Також розроблені алгоритми побудови пандіагональних квадратів, та ідеальних магічних квадратів 9 порядку. Ці результати дозволяють будувати ідеальні магічні квадрати порядків . Існують також загальні методи компонування ідеальних магічних квадратів непарного порядку . Розроблено методи побудови ідеальних магічних квадратів порядку , де , і досконалих магічних квадратів. Пандіагональні та ідеальні квадрати парного-непарного порядку вдається скомпонувати лише в тому випадку, якщо вони нетрадиційні. Тим не менш, можна знаходити майже пандіагональні квадрати. Знайдена особлива група ідеально-досконалих магічних квадратів (традиційних і нетрадиційних).

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

[ред. | ред. код]

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

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

крок 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

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

Метод терас

[ред. | ред. код]

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

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

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
.
-4 -3 -2 -1 0 1 2 3 4

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

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
.
-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

Джерела

[ред. | ред. код]

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

Посилання

[ред. | ред. код]