Магическим квадратом называется квадратная таблица с вписанными целыми числами, обладающая тем свойством что суммы чисел в каждой строке, каждом столбце и по двум диагоналям равны. Классическая задача состоит в построении магического квадрата 3 на 3 из девяти различных цифр от 1 до 9. Такой классический магический квадрат существует, и его можно построить. А вот способы построения могут быть разными.
Прямой способ основывается на переборе вариантов. Это достаточно трудоемкий путь, хотя его можно облегчить некоторыми догадками. Например, можно заметить, что сумма всех цифр от 1 до 9 равна 45. Поэтому, сумма чисел в каждой строке (и каждом столбце) должна равняться 15. Теперь рассмотрим сумму двух диагоналей и средней строки. В эту сумму входят элементы первого и третьего столбцов по одному разу, и еще центральная клетка три раза. Таким образом получаем что в центральной клетке должно стоять число 5. Ну а дальше - перебор. Цифра 9 должна где-то стоять: или на середине стороны или в углу. На против цифры 9 должна располагаться цифра 1, чтобы вместе с центральной пятеркой образовать необходимую сумму 15. И так далее...
Мы привели описание этого метода только для того, чтобы показать какой он громоздкий. Теперь посмотрим как можно решить эту задачу проще, или хотя бы, на наш взгляд, красивее. Для этого построим алгебру магических квадратов.
Правило первое. Магические квадраты можно складывать. Точно так же, как мы складываем целые числа и получаем в результате целое число, мы можем определить операцию поэлементного сложения для магических квадратов одинакового размера.
Лемма. Сумма двух любых магических квадратов есть магический квадрат.
Правило второе. Магические квадраты можно поворачивать и отражать зеркально. Таким образом, если мы найдем какой-нибудь (нетривиальный) магический квадрат - значит мы нашли целых восемь.
Теперь, чтобы наша алгебра заработала, самое время найти какой-нибудь простой магический квадрат. Самый простой - это, конечно же, нулевой магический квадрат, он состоит из 9 нулей. Также очевидно что квадрат из 9 единиц является магическим. Мы будем называть его единичным квадратом и обозначать как I. А вот квадрат из 9 двоек нам уже не нужен, потому что мы можем его получить путем сложения единичного квадрата самого с собой. Вообще, для простоты записи, мы можем определить операцию умножения квадрата на целое число n как сложение квадрата с самим собой n раз.
Операция вращения нулевого и единичного квадратов не дают ничего нового. Они переходят сами в себя. Теперь построим нетривиальный квадрат.
Задача. Расставить цифры 0. 1 и 2 в квадрат (3 на 3) так, чтобы каждая из них присутствовала в каждой строке и каждом столбце. Эта задача намного проще задачи о классическом магическом квадрате. Для ее решения не нужно ничего считать. Она легко решается из соображений симметрии. Вот решение, которое является магическим квадратом.
1 0 2
2 1 0
0 2 1
Мы будем называть этот квадрат образующим и обозначать его через E. Легко видеть, что при вращении на 90 градусов образующий квадрат порождает еще три различные квадрата, E', E'' и E'''. Проверим, что получится, например, при сложении E+E'.
1 0 2 2 0 1 3 0 3
E + E' = 2 1 0 + 0 1 2 = 2 2 2
0 2 1 1 2 0 1 4 1
Это еще не то, что нам хотелось бы. Но, интересно, как к числам из первого образующего квадрата, которые идут плотно подряд, (от 0 до 2,) добавились числа из второго квадрата, и теперь числа из их суммы перекрывают больший диапазон, от 0 до 4. Вот бы сделать так, чтобы второй квадрат поднимал числа из первого квадрата на разные ступеньки. Первая ступенька, считаем от 0 — 0, 1, 2. Вторая ступенька, считаем от 3 — 3, 4, 5. Третья ступенька — 6, 7, 8.
Для этого, второй квадрат должен состоять из чисел 0, 3 и 6. Легко видеть, что таким свойством будет обладать квадрат 3*E'.
Ответ.
1 0 2 6 0 3 7 0 5
E + 3*E' = 2 1 0 + 0 3 6 = 2 4 6
0 2 1 3 6 0 3 8 1
Ну и еще, конечно, плюс I.
Таким образом, мы решили задачу построения классического магического квадрата 3 на 3 не в терминах отдельных элементов, а с помощью построения небольшой математической теории. Если вы еще не убедились в преимуществах математического подхода, то давайте попробуем решить еще одну задачу.
Задача. Назовем квадрат 3*3 с вписанными целыми числами мультипликативным, если произведение чисел в любой строке, любом столбце и по двум диагоналям равны. Например, квадрат из 9 единиц будет мультипликативным. Требуется построить мультипликативный квадрат из 9 разных натуральных чисел, среди которых есть числа 1, 2 и 3.
Решение. Во-первых, очевидно, что по-элементное произведение двух мультипликативных квадратов есть мультипликативный квадрат. Во-вторых, заметим, что умножение ведет себя очень похоже на сложение из предыдущей задачи. И перейти от одной задачи к другой можно с помощью операции поэлементного возведения числа в степень магического квадрата. Например,
1 0 2 2 1 4
2^E = 2 ^ 2 1 0 = 4 2 1
0 2 1 1 4 2
Это - мультипликативный квадрат, в котором есть единицы и двойки в разных степенях.
Аналогично первой задаче, мы будем искать решение второй задачи в виде двух компонент, т.е. в виде произведения двух мультипликативных квадратов. Поскольку, в искомом квадрате присутствуют и двойки и тройки, то один компонент должен быть степенью 2, а другой - степенью 3. Что бы они не мешали друг другу, мы опять будем использовать E и E'.
2 1 4 9 1 3 18 1 12
2^E * 3^E' = 4 2 1 * 1 3 9 = 4 6 9
1 4 2 3 9 1 3 36 2
Это - правильный ответ. Замете, что мы в большой степени воспользовались результатами нашей теории магических квадратов.
Нет комментариев