Зміст

Вступ............................................................................................1

1.  Загальний лінійний метод побудови магічних квадратів непарного порядку..................................................................................2

1.1. Магічні квадрати і методи їх побудови.....................................2

1.2. Загальний вид лінійного методу побудови магічних квадратів..................................................................................................6

1.3. Умови правильності лінійного методу.....................................7

2.  Класичні алгоритмічні методи побудови магічних квадратів непарного  порядку...............................................................................10

     2.1. Індійський метод.......................................................................10

     2.2. Метод альфіла...........................................................................13

     2.3. Метод Баше...............................................................................15

3.  Магічні квадрати парного порядку................................................18

     3.1. Метод Раус-Болла побудови магічних квадратів парного порядку..................................................................................................18

     3.2. Побудова перестановок Т у випадку парного m....................22

     3.3. Приклади....................................................................................25

     3.4. Побудова перестановок Т у випадку непарного m................27

     3.5. Приклади....................................................................................30

Висновок...............................................................................................33

Список використаних джерел..........................................................34

Вступ

Великі вчені минулого вважали кількісні відносини основою сутності миру. Тому вивченням чисел і їхніми співвідношеннями займалася найбільш розумна частина людства. «У дні моєї юності я у вільний час розважався тим, що становив... магічні квадрати»- писав Бенджамін Франклін. А на відомій гравюрі „Меланхолія” німецький художник А.Дюрера у верхньому правому куті висить квадрат, розбитий 44 клітини, в які вписані 16 натуральних чисел.

Це дивовижний квадрат: сума чисел в кожному рядку, у кожному стовпці і діагоналях однакові. Такого виду квадрати називаються магічними, а суму S називають сталою магічного квадрату, число n – порядком квадрата.

Якщо суми по діагоналях різні, то квадрат називають напівмагічним.

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

Вивченням магічних квадратів займалися деякі  видатні математики, такі як Піфагор, Ейлер, Делаїр, Баше де Мезіріак та багато-багато інших. Вони присвятили свої роботи магічним квадратам й отримані ними результати вплинули на розвиток груп, структур, латинських квадратів, визначників,  матриць, порівнянь та на інші нетривіальні розділи математики.

Мета даної роботи - знайомство з різними магічними квадратами, а саме з магічними квадратами парного і непарного порядку, з різними методами їх побудови та прикладами.

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

1.  ЗАГАЛЬНИЙ ЛІНІЙНИЙ МЕТОД ПОБУДОВИ МАГІЧНИХ   КВАДРАТІВ  НЕПАРНОГО ПОРЯДКУ

         1.1.  Магічні квадрати і методи їх побудови.

         Числовим квадратом порядку n, де n – деяке позитивне ціле число, ми будемо називати квадрат, який розбитий на n2 кліток, в яких розміщені (в певному порядку) цілі числа від 1 до n2. Числовий квадрат будемо називати магічним, якщо сума, що отримана при додаванні чисел кожного горизонтального ряду, кожного вертикального ряду та двох діагоналей однакові. Так як квадрат порядку n містить n, скажемо, горизонтальних рядів і сума чисел кожного ряду однакова, то сума всіх чисел, розміщених в магічному квадраті, дорівнює n. З іншої сторони вона рівна:

  .   Таким чином ,     .                                       (1)    

          Умови рівності суми елементів окремих рядків, стовпців або діагоналей числу ми будемо називати умовами магічності цих рядків, стовпців або діагоналей.

         Приклад магічного квадрата порядку IV наведений на рис. 1. (Це так званий квадрат Дюрера ) Для нього, за формулою  (1),  = 34.

              Магічний квадрат II порядку не існує, III порядку існує тільки один (з найменшим натуральним числом).

              Всі інші відрізняються від даного симетріями або поворотами, або коли всі його числа збільшити чи зменшити на одне і те ж саме число; або якщо всі числа помножити чи розділити на одне й те ж ціле число.

              Магічний квадрат III порядку вважається найдавнішим. У Китаї він використовувався ще 5000р. тому, як талісман, також були гральними.

              Математиків у них зацікавила внутрішня гармонія і краса. Вони їх властивості, відкривали закономірності їх складання, класифікували їх. За кількістю клітин вони діляться на парні: 22, 42, 62 . . .  і непарні: 32, 52, . . .

Sn = - для третього порядку.

              Непарні квадрати обов’язково мають середнє (центральне)   число. У 32  середнім числом є 5. Воно обчислюється за формулою ,  тому , наприклад для S5=65, середнім числом є 13, бо  .

              Незважаючи на те, що у свій час (особливо в XVI-XVIII віках) магічні квадрати були предметом пильного вивчення ряду відомих математиків, їхня теорія ні в якій мірі не може вважатися завершеною. Звичайно, доведено, що квадратів IV порядку існує 880, а 5-го – більше 13 млн. Але дотепер невідомий ніякий загальний метод побудови всіх магічних квадратів даного порядку п і навіть невідомо їхнє число(при n). Можна лише стверджувати, що це число ділиться на 8, тому що з будь-якого магічного квадрата поворотами на 90° навколо центра й відображеннями в сторонах виходять ще 7 нових магічних квадратів.

              Зауваження. Нові магічні квадрати із даного можна також одержати і деякими іншими перетвореннями (згаданими вище).

                                          Рис.1.

              Клітини магічного квадрата порядку п ми будемо позначати парами цілих чисел (х,у) - їх координатами, де х — номер вертикального ряду, а y -- номер горизонтального ряду, на перетині яких перебуває дана клітина (мал. 2). При цьому вертикальні ряди ми нумеруємо зліва на право, а горизонтальні – знизу вверх. В якості номерів ми будемо використовувати числа

0, 1, 2, . . . , n-1,                        

тобто найменші невід’ємні значення по модулю n.

Розбиття на клітини вихідного квадрата – назвемо  його основним – ми продовжимо до розбиття на клітини всієї площини (на рис. 2 основний квадрат обведений жирною лінією). Для клітин площини ми також введемо координати (х, у), визначивши їх аналогічно координатам клітин основного квадрата, з тією лише відмінністю, що тепер ці координати можуть уже приймати будь-які цілочисельні значення. Серед всіх клітин площини клітини основного квадрата характеризуються тією властивістю, що обидві їхні координати х і y належать системі (2).

Рухаючи основний квадрат паралельно самому собі на вектори із цілочисельними координатами, що діляться на п, ми одержимо систему не налягаючих один на одного квадратів порядку п, що покривають всю площину. Дві клітини, що належать двом таким квадратам і займають відносно їх однакове положення, ми будемо називати еквівалентними. Інакше кажучи, дві клітки еквівалентні, якщо їхні відповідні координати рівносильні по модулю п. Клітини, що складають основний квадрат, попарно один одному не еквівалентні, але кожна друга клітина площини еквівалентна одній (і тільки одній) з них. Надалі еквівалентні клітки будуть грати зовсім однакову роль і будуть розглядатися як однакові. Відповідно до цього, нас в основному будуть цікавити не самі координати клітин, а їхні значення по модулю п, через що ми будемо для них писати не рівності, а рівносильності.

                                                              Рис.2.

Кожне  ціле число ми можемо записати у  вигляді , де r і s - деякі  числа   системи (2),   які однозначно визначені числом z і навпаки, однозначно визначають це число.

Наприклад, при n = 3 координати чисел

мають відповідно вигляд

При завданні деякого магічного квадрата порядку п кожній парі чисел r і  s ставиться у відповідність пара чисел x і y — координати клітини квадрата, в яку вписане число з координатами r, s. Інакше кажучи, числа х та y є функціями чисел r і s. Позначаючи ці функції буквами f  і g, ми одержимо, що x=f(r,s) і y=g(rts). Як уже говорилося, нам зручніше замість рівностей писати рівносильності по модулі п.  Таким чином кожен магічний квадрат порядку п описується двома рівносильностями виду

           де - деякі функції чисел r і s.                       (3)

Надалі будь-яку пару довільно заданих цілочисельних функцій f(r,s) і g(rts) ми будемо називати методом побудови магічних квадратів. Метод будемо називати правильним, якщо формули (3) дійсно визначають магічний квадрат.

Описані відомості задачі побудови магічного квадрата до задачі побудови пари функцій f(r,s) і g(r, s) дозволяє, зокрема, класифікувати способи побудови магічних квадратів в залежності від характеру цих функцій. Найпростішим методом побудови магічних квадратів варто вважати метод, для якого функції f(r,s) і g(rts) лінійні, тобто мають вигляд:

де  , , , , , — деякі   цілі  числа.   Такого роду методи ми будемо називати лінійними.

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

1.2. Загальний вид лінійного методу побудови магічних квадратів.

По означенню, кожен лінійний .метод побудови магічних квадратів порядку n має  вигляд:

                                                               (1)

Для практичного застосування цього методу досить істотно, що з формул (1) можна виключити координати г і s. Дійсно, очевидно, що якщо

де [ ] – знак цілої частини (найбільшого цілого числа, що міститься в даному), і

Тому формули (1) можна переписати в наступному виді, що не містять явно координат r і s:

При фактичній побудові магічного квадрата можна також писати не   рівносильності, а відповідні рівності:

                                                                        (2)

Підставляючи в ці рівності числа  , ми отримаємо координати ряду клітин, частина з яких буде обов’язково лежати за межами основного квадрата. В кожну клітину треба потім вписати відповідне число z, заміняючи одночасно клітини, що лежать поза основним квадратом, еквівалентними клітинами цього квадрата. У результаті ми одержимо деяке заповнення клітин основного квадрата числами від 1 до n2, що і буде магічним квадратом, якщо тільки метод (1) правильний.

1.3. Умови правильності лінійного методу

          Щоб лінійний метод, виражений формулами (1) п. 1.2. був правильним, необхідно в першу чергу, щоб ці формули встановлювали взаємно однозначну відповідність між координатами (г, s) чисел від 1 до п2 і координатами (х, у) клітин основного квадрата, тобто щоб для будь-яких координат х і у із цих формул можна було однозначно знайти відповідні координати г і s. Але, розвязуючи за відомими правилами рівносильності (1) п. 1.2.  відносно г і s.   ми одержимо рівносильність

                                                             (1)

Нехай виконується наступна умова:

У.1. Визначник      взаємно   простий   з  n.

Тоді для будь-яких х і у рівносильності (1) однозначно визначають координати г і s. Таким чином, при виконанні умови У. 1. формули (1) п. 1.2. встановлюється взаємно однозначна відповідність між числами від 1 до n2 і клітинами основного квадрата.

Розглянемо тепер наступну умову:

У.2. Коефіцієнти a1, a2, b1, b2  взаємно прості з n.

Виявляється, що при виконанні умови У. 2. вимога магічиості виконується відносно всіх вертикальних і горизонтальних рядів, тобто сума чисел кожного вертикального  і  горизонтального     ряду дорівнює:          

У. З.  Мають місце рівносильності

при виконанні умови У.4. зростаюча діагональ задовольняє умову магічності.

У.3/. Числа b2-b1  і  a2-a1 взаємно прості з  n.

У.4.  Мають місце рівносильності

Приходимо до іншого твердження:   при виконанні умови У.4. спадна діагональ задовольняє умові магічності.

У.4/. Числа b2+b1  і  a2+a1 взаємно прості з  n.

При виконанні умов  У.1., У.2., У. З.,  У.4.  лінійний метод  (1) п. 2.1. – правильний.

Таким чином,

правильні лінійні методи (або принаймні методи, що задовольняють умовам У.1. і У.4.) можуть існувати лише при непарному п, приклади яких ми розглянемо далі.

2

2. КЛАСИЧНІ АЛГОРИФМІЧНІ МЕТОДИ

ПОБУДОВИ   МАГІЧНИХ   КВАДРАТІВ

НЕПАРНОГО   ПОРЯДКУ

2.1. Індійський метод

Індійський метод складання магічних квадратів (іноді називається також с і а м с ь к и м) є, очевидно, самим давнім алгоритмом побудови магічних квадратів довільного непарного порядку п = 2m+1. Цей алгоритм описується наступними правилами:

1°. Числа від 1 до n2 по черзі вписуються в клітини основного квадрата.

2°. Якщо деяке правило вимагає вписати дане число в клітину, що лежить поза основним квадратом, то замість цього розглянуте число вписується в еквівалентну клітину основного квадрата.

3°. Число 1 вписується в середню клітину верхнього ряду, тобто у клітину з координатами (m, 2m).

4°. Якщо число z вписане в клітину з координатами (x, y), то наступне число z+1 вписується в клітину з координатами (x+1, y+1), тобто в клітину, суміжну   з клітиною (х, у), в напрямку зростаючої діагоналі, за умови, що ця остання клітка ще вільна від чисел.

5°. Якщо клітка з координатами (x+1, y+1) уже зайнята деяким числом, то число z+1 вписується в клітину з координатами (х, у-1), тобто в клітину, що безпосередньо примикає знизу до клітки (х, у). (Виявляється, що це завжди можливо, тобто, клітина (х, у-1) обов'язково вільна від чисел.)

На рис. 3 зображений магічний квадрат третього порядку, побудований індійським методом. Для ясності, на цьому малюнку заповнені також деякі клітини поза основним квадратом. Не описуючи докладно цю побудову, ми вкажемо лише, що число 1 вписане на підставі правил 1° й 3°, число 2 – на підставі правил 4° й 2°, число 3 – на підставі правил 4° і 2°, число 4 – на підставі правил 5° й 2°, число 5 – на підставі правила 4°, число 6 – на підставі правила 4°, число 7 – на підставі правил 5° й 2°, число 8 – на підставі правил 4а й 2° і, нарешті, число 9 — на  основі правил 4° й 2°.

                                                          Рис.3.

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

              Сутність індійського методу найкраще усвідомлюється, якщо не звертати уваги на правило 2°, тобто якщо не заміняти зовнішніх кліток еквівалентними. При такому спрощенні застосування алгоритму зводиться до заповнення клітини (т, 2т) числом 1 і наступних за нею вверх по діагоналі клітин (m+1, 2m+1), (m+2, 2m+2),…,(m+k,2m+k),.. числами 2, 3, , . , , k+1, . , . , до тих пір, поки не зустрінеться клітина, еквівалентна клітині (т,2т), що, мабуть, здійсниться при k=n. Під останньою із заповнених клітин (це буде клітка (т+n-1, 2m+n-1) = (3m, 4m) з числом n, тобто в клітині (Зт, 4m— 1), міститься число п+ 1, і з цієї клітини починається новий діагональний ряд, що закінчиться на числі 2n, так що число 2n+1 міститься під клітиною із числом 2n. Наступний діагональний ряд закінчиться на числі 3n, і т. д. Цей процес зупиниться, коли ми дійдемо до числа n2. В результаті ми одержимо п діагональних рядів чисел по п чисел в ряду, що становлять своєрідну «драбинку» (див. рис. 4 для  п = 3 і п = 5).

              Покажемо тепер, що клітина побудованої «драбинки», що містить деяке число , має координати

                                                                                                          (1)

              Дійсно, для чисел i першого діагонального ряду ці формули дають правильні координати  (т+n-1, 2m+n-1) відповідних кліток (див. вище).

                                              Рис. 4.

                      Нехай формула (1) уже доведена для чисел z = (p-1)n+1,(p-1)n+2,...,pn, що становлять р-й діагональний ряд. Тоді, згідно із цими формулами, число рп міститься в клітині (pn-p+m, pn-2p+2m+1) і, отже, відповідно до правил побудови «драбинки», число рп+1 міститься в клітині (pn—p+m, pn-2p+2m), число pn+2 – в клітині (pn—p+m+1, pn-2p+2m+1), взагалі число z=pn+k, де , — в клітині (pn-p+m+k-1, pn-2p+2m+k-1), тобто в клітині (z-p+m-1, z-2p+2m-1). 

2

                      Оскільки при z =pn + k має місце рівність, тим самим доведено, що формули (1) справедливі й для чисел                                  z =pn+1,pn+2,...,(p+1)n , що становлять (р+1)-й ряд. Тому, відповідно до принципу повної математичної індукції, формула (1) справедлива для чисел будь-якого ряду, тобто для чисел від 1 до .

              Порівнюючи доведені формули (1) з формулами (2) з попередньої глави, ми одержимо, що індійський метод є лінійним методом з коефіцієнтами               

Отже, цей   метод  для   будь-якого   п    задовольняє умову У. 1. Зрозуміло також, що для будь-якого непарного п він задовольняє  умову У. 2.  Далі, так як b2-b1=0, a2-a1=-1, то d=n, d1=1 і тому умова У. 3 зводиться до рівносильності

              Нарешті, так як b1+ bz=2, а2+ а1=-3, то при п0(mod 3) має місце умова У. 4., а при п0(mod 3) умова У. 4. зводиться до рівносильності

,  і тому також виконується.

Тим самим доведено, що

для будь-якого непарного п індійський метод правильний, тобто його застосування приводить до деякому магічного квадрату.

              Індійський метод має один недолік - для кожного непарного п він дає лише один магічний квадрат.

              2.2. Метод альфіла

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

              3°. Число 1 вписується в клітину з координатами (0,1).

          4°. Якщо число z вписане в клітину з координатами (x, у), то число z+1 вписується в клітину з координатами (x+2, y+2) за умови, що ця клітина ще вільна від чисел.  

5°. Якщо клітка  (x+2, y+2) уже зайнята, то числи z+1 вписується в клітину (x+1, y+3),  тобто   в  клітину,  яка отримана з клітини з числом    z   „ подовженим   ходом   коня ”.

                                                     Рис.5.

Приклад  магічного квадрата п'ятого порядку наведений на рис.5.

Аналітично метод альфіла записується за формулами:

звідки слідує, що

метод альфіла є лінійним методом з коефіцієнтами

Для будь-якого непарного п метод альфіла правильний.

Для кожного п метод альфіла дає тільки один магічний квадрат.

2.3. Метод Баше

Самий простий метод побудови магічних квадратів непарного порядку запропонований Баше де Мезіріаком. Він відомий також як метод терас. Деякі автори називають його індійським методом.

Рис.6.

Для побудови магічного квадрата по методу Баше варто вибрати на площині n сусідніх діагональних рядів, що містять по п клітин і таких, що середня клітина кожного ряду належить спадаючій діагоналі основного квадрата.   Клітини   лівого   верхнього ряду заповнюються знизу вверх числами 1, 2, ..., n, клітини наступного ряду – числами n+1, n+2, …, 2n  і взагалі клітини р-го, де  , - числами       р (p-1)n+1, (p-1)n+2,…, pn (див. для n = 9 рис. 7). Заповнені таким чином клітини частинами розташовані усередині основного квадрата, частинами - поза його межами, причому зовнішні клітини утворюють по бокам основного   квадрата чотири  зовсім однакові  виступи.

                                                  Рис.7.

або тераси. Легко бачити, що кожна порожня клітина основного квадрата еквівалентна одній й тільки одній клітині деякої тераси. Отже, перенісши  клітини терас в основний квадрат, що легко досягається паралельним перенесенням цих терас, ми заповнимо весь основний квадрат числами від 1 до п2. Виявляється, що отриманий таким чином числовий квадрат, є магічним.

На рис. 7 тераси, що утворилися при заповненні кліток, позначені римськими цифрами I, II, III і IV. Для побудови магічного квадрата терасу I варто пересунути паралельно самій собі так, щоб лінія AD співпала з лінією ВС, терасу II пересунути так, щоб лінія АВ співпала з лінією DC, терасу III -так, щоб лінія ВС співпала з лінією AD і, нарешті, терасу IV —так, щоб лінія DC співпала з лінією АВ. Ми отримаємо магічний квадрат, що  зображений на рис. 8.

Для доведення правильності методу Баше ми зрушимо другий зверху діагональний ряд уздовж його напрямку на п клітин вгору. Зрозуміло, що при цьому кожна клітина ряду заміниться їй еквівалентною. Далі подібним  чином зрушимо третій ряд на 2п клітин вгору і взагалі р-й ряд, де , зрушимо на (р—1) п кліток вгору.  Таким способом ми отримаємо систему клітин, яка аналітично визначається формулами

Звідси випливає, що метод   Баше   є лінійним методом з коефіцієнтами

Для цього методу       

=2, d=n, d1=1, d/=1, d1/=n.

Отже, перевірки вимагає лише виконання  першої рівносильності умови У.3. і другої рівносильності умови У.4. В даному випадку ці  рівносильності   мають  вигляд

.

Тим самим доведено, що

метод Баше правильний для будь-якого непарного п.

Отже, метод Баше приводить до магічного квадрату, для якого правила 1°, 2° й 4° збігаються із правилами індійського методу, а правила 3°  й 5° формулюються наступним чином:

3°. Число 1 вписується в клітину з координатами (т + 1, m).

5°. Якщо клітка з координатами (х+1. у+ 1} уже заповнена, то число z+1 вписується в клітину, що має координати (x+2, у), тобто в клітину, зрушену на дві клітини вправо.

Отже, метод Баше належить такому типу алгоритмічних методів, що й розглянуті раніше методи. Звичайно, крім вказаних класичних алгоритмічних методів, існують й інші, які також приводять до побудови магічних квадратів непарного порядку. Та не тільки є лінійні методи побудови магічних квадратів непарного порядку. Існує багато нелінійних методів (прикладом є квазілінійний метод Делаїра), які є також дуже цікавими. Але цих методів є дуже багато і вони дуже різноманітні, тому обмежимося лише лінійними.

3. Магічні квадрати парного порядку

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

3.1. Метод Раус-Болла побудови магічних квадратів парного порядку.

Побудова магічного квадрата порядку п=2т по методу Раус-Болла починається з того, що основний квадрат заповнюється зліва на  право і зверху вниз числами від 1 до п2 в їхньому природному порядку. Таким чином, у перший зверху горизонтальний ряд вписуються числа 1, 2, ...,п, у другий — числа n+1, n+2, …, 2n і взагалі в р-й горизонтальний ряд, де , вписуються числа (р—1) n+1,  (р —1)n+2, . . . ,pn.

Отриманий числовий квадрат не є, звичайно, магічним. Однак неважко побачити, що

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

.

Дійсно,   на   спадній   діагоналі  стоять, очевидно, числа

1,n+2, 2n+3,…,(p-1)n+p, …, n2,  сума  яких дорівнює 1+2+…+n+n(1+2+…+n-1) = .

Аналогічно на зростаючій діагоналі стоять числа   n, 2n-1, 3n-2, …, pn-p+1, …, n2-n+1  зі сумою  n(1+2+…+n)-(1+2+…+n-1)= .

              Що ж стосується  горизонтальних рядів, то сума sp чисел р-го (рахуючи зверху) горизонтального ряду виражається  формулою

sp=.

Змінивши   в  цій   формулі  р  на n-р+1, ми одержимо, що

Sn-p+1=m(2m+1)+4m2(2m-p), звідки слідує, що

sp + Sn-p+1 = 2m(2m+1)+4m2(2m-1)=2

де                            .

Помітивши, що ряди з номерами р и n-p+1 симетричні відносно середньої лінії квадрата, ми одержимо звідси, що хоча горизонтальні ряди й не задовольняють умові магічності, але

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

У відповідних один одному клітинах двох симетричних горизонтальних рядів перебувають числа

(р — 1) n+i,   (п-р)п+i,

різниця tp яких дорівнює (n-2p+1)n i, отже, та сама для   всіх   клітин.              Тому Sn-p+1 - sp = ntp

звідки  випливає, що   Sn-p+1 - mtp = sp+ mtp

Із цієї рівності слідує,  що

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

Таким чином, обравши у кожній парі симетричних горизонтальних рядів по m пар взаємно симетричних клітин і переставивши числа кожної пари, ми одержимо числовий квадрат, для якого умова магічності буде виконано для всіх горизонтальних рядів.

Однак властивості магічності діагоналей може при цьому порушитися.

Аналогічно проводимо побудову і для вертикальних рядів. Дійсно, у р-му (рахуючи зліва) вертикальному ряді стоять числа

р, р+n, р+2п, . . ., р+п(п — 1), сума що виражається формулою

= +np=2m2(2m-1)+2mp.

Звідси слідує, що + .

Далі, у відповідних один одному клітинах двох симетричних (щодо середньої вертикальної лінії) рядах перебувають числа

p + (i  - 1)n,      in -  p+1,

різниця яких =n - 2p+1  не залежить від і. Отже, - =,

і тому   - m=+ m.

              Як і для горизонтальних рядів, звідси слідує, що,

вибравши в кожній парі симетричних вертикальних рядів по т-пар взаємно симетричних клітин і переставивши числа кожної пари, ми одержимо числовий квадрат, для якого умова магічності буде виконана для всіх вертикальних рядів.

Однак при цьому знову може порушитися магічність діагоналей.

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

Існує така перестановка Т клітин   основного квадрата, що

1о. Якщо клітина під впливом перестановки Т переходить у клітину , то, навпаки, клітина під впливом перестановки  Т переходить у клітку :

=Т;

2о. У кожному ряді (як горизонтальному, так і в вертикальному) існує точно т клітин, які під впливом перестановки Т переходять у т клітин симетричного ряду;  інші клітки цього ряду під впливом перестановки Т залишаються на місці;

3о. Якщо клітка належить одній із діагоналей, то клітина Т також   належить   тій  же діагоналі.

Умова 1° називається умовою і н в о л ю в т и в н о с т і. З нього слідує, що система всіх клітин, що не залишаються під впливом перестановки Т на місці, розпадається на пари (,Т) взаємно переміщуваних клітин. Завдання системи цих пар, мабуть, повністю визначає перестановку  Т.

Із усього сказаного вище  випливає наступне П р а в и л о:

Для побудови магічного квадрата парного порядку п варто вибрати перестановку Т, що задовольняє перерахованим вище умовам 1°, 2° й 3°, і потім, заповнивши клітини основного квадрата числами 1, 2, ...,n2 у їхньому природному порядку, переставити між собою числа, що перебувають у клітинах, що  взаємно переміщувані перестановкою Т.

При цьому умова 2°, накладена на перестановку Т, забезпечить магічність горизонтальних і вертикальних рядів, а умова 3° забезпечить   збереження   магічності   діагоналей.

Таким чином, для повного обґрунтування викладеного методу побудови магічних квадратів нам залишається лише довести існування необхідних перестановок Т.  Ми зробимо це в наступних розділах, вказавши практичний прийом їхньої побудови.

3.2. Побудова перестановок Т у випадку парного m

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

переводить у конфігурацію            

                                                        .

Зрозуміло, що елементарна перестановка S володіє властивостями 1о і 3о перестановки Т.

Припустимо тепер, що число m парне, m=2l, і що в основному квадраті відзначено 2m2 = 8l2  клітин, що задовольняють наступним умовам:

а) відзначені клітини розпадаються на 2l2 четвірок, що володіють вказаними вище властивостями симетрії ;

б) в кожному горизонтальному чи вертикальному ряду знаходиться точно m відзначених клітин.

Кожній із передбачених умовою а) четвірок відповідає своя елементарна перестановка S. Очевидно, що якщо ми   зробимо   всі   ці перестановки       одночасно,   то  в   результаті   ми   одержимо   деяку   перестановку    Т,   що володіє всіма   необхідними    властивостями   1° , 2° і 3°.

Таким чином, питання про побудову перестановки Т зводиться до питання про побудову системи клітин, що задовольняють умовам  а), б).

                                                             Рис.8.

Гарний метод побудови такої системи кліток належить французьким математикам Деланэ й Мондезиру. Відповідно до цього методу, для того щоб побудувати необхідну систему клітин, потрібно на нескінченно розкинуту в усі сторони «шахівницю», кожне поле якої вчетверо більше клітини основного квадрата, накласти основний квадрат так, щоб його центр потрапив у центр одного з полів дошки і відзначити клітини, що попадають на поля одного кольору (див. мал. 8 для т=4; на цьому малюнку зображений також відповідний магічний квадрат).

Всі системи клітин, що задовольняють умовам а) і б) не вичерпуються системами клітин, які будуються за методом  Деланэ й Мондезира. Загальний метод побудови таких систем полягає в тому, що основний квадрат розбивається на чотири однакових квадрати порядку т і в лівому верхньому квадраті (будемо позначати цей квадрат символом К) вибирається така система 2l2 клітин, що:

а) у кожному горизонтальному або вертикальному ряді квадрата К перебуває точно l  клітин цієї  системи.

Зрозуміло, що якщо ми для кожної клітини зазначеної системи побудуємо клітини, що симетричні їй відносно центра і обох середніх ліній основного квадрата, то в результаті ми в основному квадраті одержимо систему 8l2 клітин, що задовольняє умовам а) і б). Таким чином, усе зводиться до побудови в квадраті К  системи 2l2 клітин, що володіють властивістю а).

Побудову такої системи можна здійснити багатьма різними способами. Наприклад, можна в першому лівому вертикальному ряді квадрата К довільно вибрати l клітин, які перебувають у горизонтальних рядах, що мають (рахуючи зверху), скажемо, номера і1, і2, ..., it. Потім в другому вертикальному ряді вибрати клітини з номерами і1+1, і2+1, ..., it+1. і взагалі в р-му ряді, де , вибрати клітини з номерами і1+р-1, і2+р-1, ..., it+р-1. При цьому, якщо яка-небудь із клітин виявиться поза квадратом К, то вона повинна бути замінена клітиною, еквівалентною їй відносно цього квадрату. Тим самим у кожному вертикальному ряді буде обрано точно l клітин. Так як для будь-якого k = 1, 2, . . .,l числа ik, ik+1, . . ., ik+p-1, . . .,  ik+m-1     становлять повну систему відрахувань по модулі т, то для будь-якого і = 1,2, . . .,m існує таке число рі,к = 1, 2, . . ., т, що

                                         ,

звідки безпосередньо слідує, що в кожному, скажемо, і-му горизонтальному ряді також буде знаходитися точно l обраних клітин (а саме, клітин із вертикальних рядів з номерами pi,1,  pi,2, . . ., pi,l).

Цей спосіб побудови потрібної системи клітин, хоча й досить загальний, але все-таки не дозволяє одержати всі такі системи. Інші системи можна, наприклад, одержати, повертаючи квадрат К на чверть окружності в напрямку за часовою стрілкою або проти. Ще дві системи можна одержати, розбиваючи квадрат К на чотири однакових квадрати і відзначаючи або клітини верхнього лівого і нижнього правого квадратів, або клітини верхнього правого і нижнього лівого квадратів. Можна, нарешті, скористатися методом Деланэ й Мондезира (стосовно до квадрата К). Підсумовуючи все сказане, ми одержуємо наступне

  П р а в и л о:

Для того щоб у випадку парного т побудувати перестановку Т, що володіє властивостями 1о, 2° й 3°, зазначеними в попередньому пункті, потрібно:

1) розділити основний квадрат на чотири однакових
квадрата порядку m;

                            2) побудувати  (наприклад,   одним  із   описаних   вище
способів)   у   лівому   верхньому   квадраті   систему   клітин, що володіють   властивістю   а),   і   відзначити   їх   деяким знаком (скажемо, зірочкою);

                            3) для кожної з побудованих клітин знайти в основ­ному  квадраті   клітини,   симетричні   їй   щодо центра і обох середніх ліній, і   відзначити   ці клітини тим же знаком.

Після того як це зроблено, перестановка Т визначається як перестановка, що взаємно переміщає відзначені центральносиметричні клітини і залишає всі невідмічені клітини на місці.

3.3.  Приклади

Для кращого з'ясування викладеного методу побудови магічних квадратів порядку  п = 2т при т парному проілюструємо цей метод на прикладах.

Нехай спочатку п = 4 а, отже, т = 2, l= 1. У цьому випадку квадрат К  має другий порядок і відмітити в ньому клітини ми можемо лише двома способами:

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

Переставивши в першому із цих квадратів середні вертикальні ряди, ми одержимо квадрат Дюрера, зображений на мал. 1,

Нехай тепер п=8 і, отже, m = 4, l= 2.У цьому випадку відмітити клітини квадрата К можна досить багатьма способами (читачеві рекомендується самостійно знайти точне число цих способів). Ми зробимо це, слідуючи зазначеному вище загальному методу, приймаючи і1 = 2, і2=3. У результаті ми одержимо наступне   розміщення зірочок:

Після   цього   ми   заповнюємо   основний   квадрат   восьмого порядку числами від 1  до 64 у   їхньому   природному   порядку і розміщуємо в ньому зірочки:

Зробивши взаємну заміну центральносиметричних клітин, відзначених зірочками, остаточно одержимо магічний квадрат.

2

3.4. Побудова перестановок Т у випадку непарного   m

Якщо число m непарне, m=2l+1, то побудова перестановок Т виконується аналогічно, але є трохи складнішою. Виявляється,  що в цьому випадку описаних в попередньому розділі елементарних перестановок для побудови перестановок Т уже недостатньо. Ми введемо ще елементарні перестановки U, що взаємно переміщують дві клітини, симетричні відносно середньої горизонтальної лінії основного квадрата, і елементарні перестановки V, що взаємно переміщують дві клітини, симетричні відносно середньої вертикальної лінії основного квадрата. (Передбачається, що всі інші клітини основного квадрата перестановки U й V залишаються на місці.) Зрозуміло, що перестановки U і V володіють властивістю 1° від перестановки Т, що ж стосується властивості 3о, то вони володіють ними тоді і тільки тоді, коли клітини, що переставляються, не належать діагоналям.

Помітимо, що будь-яка перестановка S зводиться, як легко бачити, до виконання двох перестановок U  і двох перестановок V. Однак нам буде зручно розглядати перестановки S незалежно від перестановок U й V.

Припустимо тепер, що в   основному квадраті відзначені три групи клітин, що задовольняють наступним умовам:

а) клітини  першої  групи   ( що складає   з   4ml   клітин)

розпадаються на ml четвірок, що володіють  зазначеними вище властивостями симетрії;

                            б) клітини другої й третьої груп (що складається кожна з 2т  клітин)  розпадаються  на  т   пар, що   складаються  із клітин,    симетричних   щодо   середньої   горизонтальної (відповідно до вертикальної)   лінії основного квадрата;

                            в) у  кожному   горизонтальному   й   вертикальному   ряді перебуває точно    m = 2l+1  відзначених кліток,  причому 2l з них   належать   першій   групі,    а одна — другій групі,  якщо    розглянутий    ряд  -  горизонтальний,    і третій групі, якщо цей ряд  вертикальний;

                            г) жодна із клітин другої й третьої груп не належить ні одній з діагоналей.

Кожній з передбачених умовою а) четвірок відповідає своя елементарна перестановка S, а кожній з передбачених умовою 6) пар — елементарна перестановка U, якщо ця пара складається із клітин другої групи, і елементарна перестановка V, якщо ця пара складається із клітин третьої групи. Результат застосування всіх цих перестановок являє собою деяку перестановку Т, що    володіє властивостями 1° (очевидно), 2° (в силу умови в) і 3° (в силу умови г).

                Таким чином, питання про побудову перестановки Т зводиться до питання  про побудову в основному квадраті трьох груп клітин, що задовольняють умовам   а)-г).

Для того щоб побудувати такі групи клітин, ми, як і в попередньому розділі, розіб'ємо основний квадрат на чотири однакових квадрати порядку m і припустимо, що в лівому верхньому квадраті К вибрані три групи клітин, що  складаються відповідно з ml, m й m клітин, і володіють наступними властивостями:

) в кожному горизонтальному або вертикальному ряді квадрата К перебуває точно l клітин першої  групи;

) в кожному горизонтальному ряді квадрата К  перебуває точно одна клітина другої групи, а в кожному вертикальному ряді — точно одна клітина третьої  групи;

) жодна клітина другої або третьої групи не належить спадній діагоналі квадрата К.

Зрозуміло, що якщо ми для клітин першої групи побудуємо в основному квадраті клітини, симетричні відносно центра й обох середніх ліній основного квадрата, для клітин другої групи — клітини, симетричні відносно середньої горизонтальної лінії основного квадрата, і, нарешті, для клітин третьої групи — клітини, симетричні їм щодо середньої вертикальної лінії основного квадрата, то   отримані три групи клітин будуть задовольняти умовам а)-г). Таким чином, усе зводиться до побудови в квадраті  К трьох   груп   клітин, що   володіють властивостями ) - ).

Побудову цих груп можна здійснити, наприклад, таким способом. У першому зліва вертикальному ряді квадрата К вибираємо l+2 клітин. Нехай ці клітини лежать у горизонтальних рядах з номерами і1, і2, ..., it, j, k (номера ми, як і вище, рахуємо зверху вниз). Клітини можна вибирати зовсім довільно, з єдиним обмеженням, щоб ні число j, ні число k не дорівнювало одиниці. Зрозуміло, що при l1, тобто при m 3, цю умову завжди можна задовольнити. Далі, у другому вертикальному ряді вибираємо клітини, що лежать у горизонтальних рядах з номерами і1+1, і2+1, ..., it+1, j+1, k+1, у третьому вертикальному ряді — клітини, що лежать у горизонтальних рядах з номерами і1+2, і2+2, ..., it+2, j+2, k+2, і взагалі в  р-му вертикальному ряді, де , вибираємо клітини, що лежать у горизонтальних рядах з номерами і1+р-1, і2+р-1, ..., it+р-1, j+р-1, k+р-1. При цьому, якщо яка-небудь із клітин виявиться поза квадратом К, то її варто замінити клітиною, еквівалентною їй стосовно цього квадрата. Клітини, що відповідають числам виду is+ p— 1, ми віднесемо до першої групи. Той факт, що вони задовольняють умові ), перевіряється дослівно так само, як і відповідне твердження в попередньому розділі. Клітини, що відповідають числам виду j+p-1, ми віднесемо до другої групи. Вони задовольняють умові ), тому що числа виду j+p—1 становлять повну систему лишків за модулем m, і умові у), тому що j1, Нарешті., клітини, що відповідають числам виду k+р—1, ми віднесемо до третьої групи. Вони задовольняють умові ) по побудові, а умові у) через те, що к1.

На практиці клітини трьох груп зручно відмітити трьома різними значками, наприклад, зірочкою * , прямим хрестиком  + і косим хрестиком  .

Виключений вище випадок l= 0, тобто випадок п=2, інтересу не представляє, тому що, як легко бачити, у цьому випадку магічних квадратів не існує.

Аналізуючи все сказане,  ми одержимо наступне

Правило. Для того щоб у випадку непарного m>1 побудувати перестановку Т, що володіє зазначеними з попереднього розділу властивостями 1°, 2° й 3°. потрібно

1) розділити основний квадрат на чотири однакових квадрати порядку т;

         2) побудувати (наприклад, описаним вище способом) в лівому верхньому квадраті три групи клітин, що володіють властивостями ),), у) , і відмітити клітини першої групи знаком *, другої — знаком +. і третьої — знаком ;