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

300000

84060
61655

Цілі Навчання

Вступ

Визначення:

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

Типове питання:
Яким числом потрібно замінити знак питання, щоб завершити Магічний Квадрат?
```
     
	15  *  35
	50  *   ?
	25  *   *
			
```
Це легко розв'язати. Сума в кожному рядку дорівнює 15 + 50 + 25 = 90. З діагоналі випливає, що число посередині дорівнює 90−25−35 = 30, а з 2-го рядка: 50+30+?=90 → ? = 10.

Як би ви розв'язали Магічний Квадрат із меншою кількістю заданих чисел, як наведено нижче?
```
	?   *   *
	*   *  47
	*  63   *
			
```
Який типовий спосіб розв'язання цього завдання? Можна ввести змінні
```
	P   Q   R
	U   V  47
	X  63   Z
	
```
і сформулювати всі умови як рівняння, такі як
```
	P+Q+R = U+V+47 = X+63+Z = P+U+X = Q+V+63 = R+47+Z = P+V+Z = R+V+X,
	
```
розв'язати цю систему рівнянь, усунувши всі невідомі, крім P, щоб отримати одне рівняння для P і розв’язати його. Маємо 7 рівнянь для 7 невідомих.

Надалі ми хочемо розв’язувати Магічні Квадрати без необхідності розв’язувати такі системи рівнянь.

Загальні Відношення та Приклади

Давайте пошукаємо прості співвідношення між числами у Магічному Квадраті.

Оскільки квадрат має багато симетричних перетворень (4 повороти + дзеркальне відображення та їх комбінації), давайте визначимо величини, які не змінюються за таких перетворень. Наприклад, якщо ми маємо такий квадрат:
```
	P  Q  R
	U  M  W
	X  Y  Z
	
```
то величини, що не змінюються при повороті та дзеркальному відображенні, наступні:
```
	C = сума значень кутів		(= P+R+X+Z)
	E = сума середніх значень сторін		(= Q+U+W+Y)
	M = середнє значення		(= M)
	S = сума в кожному рядку		(= P+Q+R = P+U+X = X+M+P = ...) .
			
```
Які співвідношення можна вивести для цих величин?
- Неважко знайти наступні співвідношення між C, E, M, S, виключивши змінні P, Q, R, U, W, X, Y, Z із наведених рівнянь.
  
  Лема 1:
```
	2C + E = 4S        (1)
	M + C + E = 3S     (2)
	C + 2M = 2S        (3)
	C − M = S          (4)
	3M = S             (5)
						
```
  Доведення.
  
  Наведені вище співвідношення випливають з наступного:
  
  (1) з додавання значень 4 сторін
  (2) з додавання всіх чисел
  (3) з додавання сум 2х діагоналей
  (4) з (1) − (2)
  (5) з (3) − (4)
  
  ▢
  
  Перевірте (1), (2) та (3), замінивши C, E та S на їх суми.
  
  Чим вони можуть допомогти? Наприклад, співвідношення (5) достатньо для розв’язання наступних прикладів.
  
  Приклад:
```
	3  2  7
	*  ?  *
	*  *  *
						
```
  Розв’язання
  
  Оскільки в 1-му рядку відомо всі 3 числа, ми знаємо, що S = 3 + 2 + 7 = 12. Отже, за (5), ? = 12/3 = 4.
  
  Приклад:
```
	11  *  4
	*  6  *
	*  ?  *
						
```
  Розв’язання
  
  Нехай Q = середнє значення 1-го ряду. Тоді за (5) 11 + Q + 4 = 3×6 → Q = 18−4−11 = 3.
  
  Таким чином, ? = 18−6−3 = 9.
  
  Приклад:
```
	*  *  5
	*  9  *
	?  *  *
						
```
  Розв’язання
  
  Згідно (5), ?+9+5 = 3×9 = 27 ⇒ ? = 27−9−5 = 13.
  
  Приклад:
```
	*  *  5
	*  ?  *
	9  *  *
						
```
  Розв’язання
  
  Згідно (5), 5+?+9 = 3×? ⇒ 14 = 2×? ⇒ ? = 14/2 = 7.
  
  Приклад: Наступна головоломка містить цифри 7, ..., 15. Яке значення Р?
```
	P   *   *
	*   *   *
	*   *  14
						
```
  Розв’язання
  
  Не знаючи, що цей Магічний квадрат заповнений цілими числами від 7 до 15 включно, одного заданого числа було б недостатньо. Але з цією інформацією та згідно (5),
  
  3S = (7+15) + (8+14) + (9+13) + (10+12) + 11 = 4×2 + 11 = 99 ⇒ S = 33 ⇒ M = 11 ⇒ 14 + 11 + P = 33 ⇒ P = 8.
  
  Як щодо наступної задачі?
```
	?   *   *
	*   *  47
	*  63   *
						
```
  Для розв’язання нам потрібно більше співвідношень.

Загальна теорія

Які найпростіші магічні квадрати приходять вам на думку?
Наша стратегія буде полягати в тому, щоб розпочати з найпростішого Магічного Квадрата
```
	0 0 0
	0 0 0        (6)
	0 0 0
	
```
і знайти “перетворення”, тобто методи перетворення Магічного Квадрата на інший Магічний Квадрат. Перша така деформація полягає в додаванні одного і того ж значення 1 до всіх полів:
```
	1 1 1
	1 1 1        (7)
	1 1 1
				
```
Отримуємо інший Магічний Квадрат. Які ще є загальні перетворення?
Спочатку дамо визначення „лінійному” математичному об’єкту.

Визначення:
Математичний об'єкт називається лінійним, якщо
- сума двох таких об'єктів дає інший такий об'єкт, і
- множення такого об'єкту на число дає інший такий об'єкт.
Теорема 1:
Магічніі Квадрати - це лінійні математичні об’єкти.

Хочете спробувати довести цю теорему?
Доведення.
1. Так як додавання комутативне: Якщо 2 магічні квадрати
```
	a11 a12 a13
	a21 a22 a23        (8)
	a31 a32 a33
	
```
  та
```
	b11 b12 b13
	b21 b22 b23        (9)
	b31 b32 b33
	
```
  Додати, то
```
	a11+b11  a12+b12  a13+b13
	a21+b21  a22+b22  a23+b23        (10)
	a31+b31  a32+b32  a33+b33
	
```
  ми також отримаємо Магічний Квадрат, оскільки, наприклад, перші два рядки (10) мають рівні суми.
```
	a11+b11 + a21+b21 + a31+b31
	= a11+a21+a31 + b11+b21+b31      (комутативність додавання)
	= a12+a22+a32 + b12+b22+b32      (оскільки (8) та (9) є Магічними Квадратами)
	= a12+b12 + a22+b22 + a32+b32    (що ми хотіли показати)
							
```
  Подібним чином можна показати рівність сум інших рядків (10).
2. Відповідно до розподільного закону, якщо (8):
```
	a11 a12 a13
	a21 a22 a23
	a31 a32 a33
	
```
  є Магічним Квадратом, то
```
	b×a11  b×a12  b×a13
	b×a21  b×a22  b×a23
	b×a31  b×a32  b×a33
	
```
  також є Магічним Квадратом, тому що, наприклад, якщо
```
	a11 +   a12 +   a13  =    a21 +   a22 +   a23  то 
	b×(a11 +   a12 +   a13) = b×(a21 +   a22 +   a23)  і 
	b×a11 + b×a12 + b×a13  =  b×a21 + b×a22 + b×a23 .
							
```
  ▢
Висновок 1.1:
Застосування цієї теореми означає, що віднімання середнього значення з усіх полів Магічного Квадрата (тобто віднімання М помноженого на Магічний Квадрат (7)) дає Магічний Квадрат із середнім значенням 0.

Повернімось до нашої проблеми пошуку інших перетворень. Наступне повинно зберігати 0 як центральне значення, щоб не перешкоджати перетворенню −M×(7).
Давайте змінимо верхнє ліве значення на 1 (найменше можливе значення):
```
	1  *  *
	*  0  *
	*  *  *
			
```
Оскільки M = 0, то S також має дорівнювати нулю, тобто
```
	1  *  *
	*  0  *
	*  * −1
			
```
У верхньому правому куті може залишитися 0, але тоді всі інші зміни будуть фіксованими:
```
	+1 −1  0
	−1  0 +1        (11)
	0 +1 −1
			
```
Це Магічний Квадрат.

Ми отримуємо чергове перетворення Магічного Квадрата шляхом перетворення симетрії. Це означає, що будь-яке дзеркальне відображення або обертання Магічного Квадрата також дає Магічний Квадрат. Дзеркальне відображення відносно головної діагоналі не дає новий Магічний Квадрат, а поворот дає:
```
	0 −1 +1
	+1  0 −1        (12)
	−1 +1  0
			
```
Тепер ми застосовуємо теорему 1 тричі.
Отримавши Магічний Квадрат, спочатку віднімаємо квадрат a22×(7), щоб середнє значення стало рівним нулю. Потім віднімаємо з нового квадрата квадрат a11×(11) так, щоб лівий верхній кут став рівним нулю. Значення по-середині залишається нулем, оскільки a11×(11) має середнє значення 0. Тоді віднімаємо квадрат a13×(12)так, що правий верхній кут стає рівним нулю. При цьому середнє значення та лівий верхній кут залишаються рівними нулю, оскільки ці поля дорівнюють нулю в a13×(12). Отже, це означає, що з будь-якого Магічного Квадрата можна відняти квадрати кратні квадратів (7), (11) та (12), щоб отримати Магічний Квадрат виду
```
	0 * 0
	* 0 *
	* * *
	
```
з S рівним нулю (оскільки середнє значення дорівнює нулю). Легко показати, що Магічний Квадрат є таким:
```
	0 0 0
	0 0 0
	0 0 0
			
```
Але це означає, що кожен Магічний Квадрат можна записати як суму, кратну квадратам M×(7) + A×(11) + B×(12).

Теорема 2:
Будь-який Магічний Квадрат можна записати як
```
	M+A     M−A−B   M  +B
	M−A+B     M     M+A−B        (13)
	M  −B   M+A+B   M−A  .
			
```
Доведення

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

▢

Більш математичною мовою можна сказати, що:
Магічні Квадрати (7), (11) та (12) - це повний набір генераторів для всіх Магічних Квадратів.
Тепер, коли ми знаємо базис усіх магічних квадратів, чи є ще щось корисне для розв’язування задач типу Магічний Квадрат? З допомогою правила (5): 3M = S, ми знайшли просте і корисне співвідношення між окремою складовою квадрата і S. Ось ще два співвідношення.

Лема 2:
Кожне значення кута є середнім значенням 2 значень, прилеглих до протилежного кута.

Доведення

априклад, для лівого верхнього кута в (13), M+A = ((M+A+B)+(M+A−B))/2, і так само для інших 4 кутів.

▢

Це просте правило миттєво вирішує одне із попередніх завдань
```
	?  *  *
	*  * 47
	* 63  *
	
```
скоротивши розв’язання до ? = (63+47)/2 = 55. Ось інше співвідношення:

Лема 3:
Для кожного рядка, що проходить через центр квадрата, середнє значення M - це середнє значення інших двох значень у рядку.

Доведення

Доведення. За допомогою (13).

▢

Висновок 2.1:
Якщо не вказано нічого, крім одного числа, тоді жодне інше число визначити не можна.

Висновок 2.2:
Якщо дано 2 числа і можна застосувати лему 2 або 3, то 3-тє число фіксоване.

Висновок 2.3:
Якщо дано 3 числа, які не пов’язані між собою лемами 2 або 3, тоді ці 3 числа визначають весь Магічний Квадрат.

Висновок 2.4:
Усі задачі типу Магічний Квадрат легко розв'язати, обчисливши M, A і B з відомих чисел, і підставивши значення M, A і B до (13), щоб знайти всі інші числа.

Чи Найважчий Рівень Складності Насправді Такий Важкий?

Коли ми дивимося на Магічний квадрат (13), ми бачимо, що існує 3 незалежних параметри A, B і M. Якщо вказано лише 2 (а для найскладнішого рівня центральне значення = M ніколи не дається), тоді M можна вибрати вільно а інші 2 задані значення визначали б A і B.

Яке значення M робить завершення Магічного Квадрата найпростішим?
- Вибравши M = 0 як значення в центрі, всі рядки через центр можна завершити, просто змінивши знак протилежного числа, щоб в сумі отримати 0. Для знаходження решти чисел потрібно виконати лише різниці/суми двох числа.
  
  Приклад:
```
	*   80    *
	*    *   56
	*    *    *
						
```
  Розв’язання
  Спочатку ми можемо застосувати лему 2, щоб отримати значення в нижньому лівому куті - середнє (80 + 56) / 2 = 136/2 = 68:
```
	*  80   *
	*   *  56
	68   *   *
	
```
  Потім, після додавання 0 в центр та дзеркального відображення чисел за допомогою зміни знаків отримаємо:
```
	*   80  −68
	−56    0   56
	68  −80    *
	
```
  Тепер, оскільки всі суми дорівнюють 0, лівий верхній кут повинен бути 68−80 = −12. Тому найпростішим розв’язком цього прикладу є:
```
	−12   80  −68
	−56    0   56
	68  −80   12
							
```
Економія часу
- Якщо ми знаємо всі числа в одному рядку і 2 числа в рядку, який перетинає його, то ми можемо трохи пришвидшити обчислення, особливо коли числа більші.
  
  Приклад:
```
	P  *  *
	U  ?  W
	X  *  *
	
```
  де P, U, X, W відомі, і ми хочемо знайти?.
  Ми знаємо, що P+U+X = U+?+W, а отже, P+X = ?+W. Таким чином,? = P+X−W.
  Що ще можна зробити, так це перевірити, які з P, X найближчі до W, скажімо, P, а потім обчислити? = X+(P−W). Це набагато швидше, ніж S = P+U+X, ? = S−U−W, особливо якщо P−W - невелике. Це можна по-практикувати на рівні Мунтжак.

Підсумки

Ми засвоїли загальний підхід до розв’язання складної математичної задачі (тут можна знайти найпростіші Магічні Квадрати), який має симетрії (тут повороти та дзеркальні симетрії), а також спеціальний розв’язок (тут Магічний квадрат (11)), яке не має цих симетрій ((11) не є результатом повороту), тобто, коли застосовується операція симетрії, генерується новий спеціальний розв’язок (тут (11) → поворот → (12)).
Крім того, ми побачили, як у задачах для лінійних об'єктів можна отримати загальний розв’язок, додавши числа кратні повному набору спеціальних розв'язків (тут кожен Магічний Квадрат може бути записаний як сума кратних (7), (11) та (12 )).

Тепер ви можете швидко виграти гру "Магічний Квадрат" ... чесно!