MagicSquare1. Модель Бубса и Мумса
Прекрасная статья для прекрасных людей. Ещё одна.
Знаете, что такое магический квадрат? Такая табличка с циферками. Непростая табличка, а, например, такая:
Что в ней такого крутого? Сумма чисел во всех строках, столбцах и диагоналях одинакова. Это, в общем-то, и есть определение магического квадрата.
Такие штуки мы сегодня будем изучать. Конечно, их уже изучали до нас. Много-много раз. И, в отличие от нас, изучали разные квадраты — мы будем изучать только квадраты 3 на 3. Горжусь, кроме прочего, тем, что всё написанное ниже и в следующих статьях мы прошли сами, а потом уже углубились в чужие исследования.
Наша цель — собрать как можно больше разнообразной информации о потенциально существующем магическом квадрате из квадратных чисел. Этим мы занимались с Нерегулярным автором, но наши исследования разошлись. Везде, где то, что я пишу, будет пересекаться с его исследованием, я попытаюсь отразить его версию. Может быть, когда-нибудь он напишет свой вариант сам
Итак, начнём.
Для начала, чтобы нам жилось максимально обобщённо, в общем виде будем записывать наш квадрат в виде таблички из девяти букв:
Сумма строки/столбца/диагонали в общем и целом называется «магическая константа». Будем обозначать её буквой М. Типа Мынка. Ну или Магическая константа. Что вам больше нравится.
Тогда запишем все суммы, проходящие через E.
В принципе, детсадовский уровень. Ничего сложного. Что вы видите? Что во всех этих штуках, к нашему удивлению, есть буква Е. Это, конечно же, очень неожиданно, мы взяли все суммы, проходящие через E, и во всех этих суммах оказалась Е. Я шокирован.
Ну давайте мы все эти ваши Е вычтем из всех этих сумм.
Ну и чтобы жизнь совсем была сказкой, введём временную замену N = M-E.
Идеально.
Что мы сделаем теперь? Теперь мы возьмём и сложим первую и третью строки. А чтобы жизнь не прекращала быть сказкой, в скрине я продублирую сам квадрат:
Вы должны быть счастливы. Этот скрин — самая цветная штука из всех, что вам доводилось видеть в этой мрачной жизни. Я его даже на обложку статьи поставлю.
Что же мы видим? 2M = 3N. Раскрываем нашу временную замену:
Ура, мы выразили всё через E. Мы такие молодцы. Теперь мы можем выкинуть эти замены до лучших времён и заметить два факта:
— Магическая константа любого квадрата равна утроенному числу, стоящему в центре квадрата
— Сумма двух противоположных элементов равна удвоенному числу, стоящему в центре квадрата
И, действительно, возьмём любой магический квадрат 3 на 3:
7+12+14 =
18+11+4 =
8+10+15 =
7+18+8 =
12+11+10 =
14+4+15 =
7+11+15 =
8+11+14 =
33 = 3*11
7+15 = 8+14 = 18+4 = 12+10 = 22 = 2*11
Отлично, идеально.
Следующий шаг. Теперь, когда мы связали противоположные элементы квадрата, будем называть их сопряжёнными. То есть, A сопряжено с J, B с H, C с G, D с F. Всё легко.
Если мы предполагаем, что все элементы квадрата различны [а мы предполагаем], то из двух сопряжённых элементов один больше, а другой меньше. А поскольку в сумме они равны 2Е, то один из них больше, чем Е, а другой меньше, чем Е.
Вот давайте все большие будем отмечать буквой Б, а все маленькие буквой М.
Предположим, что А большое. Тогда J автоматически маленькое.
А ещё предположим, что B тоже большое. Тогда H автоматически маленькое:
Теперь получается, что наверху у нас 2Е+что-то ещё. Значит, С должно быть маленьким, чтобы в сумме вышло 3Е. G, в таком случае, большое.
Если вы поняли логику, то уже знаете, что D маленькое, а F большое.
Отлично, мы всем всё расставили. В процессе мы сделали два предположения: насчёт А и насчёт В. Если мы на секунду уберём все буквы кроме б, м и Е, то получим штуку:
Если бы мы предположили, что А — большое, а В — маленькое, то получили бы поворот этого квадрата по часовой стрелке на 90º или отражение относительно центральной горизонтали. Если бы предположили, что А маленькое, а В — большое, то тоже получили бы поворот или отражение. Если бы предположили, что оба маленькие, то получили бы двойной поворот.
В общем-то, вполне очевидно, что магический квадрат можно крутить и отражать, и он всё равно останется магическим. А значит, такая модель единственная с точностью до изоморфизма.
Углы квадрата находятся в изначально равных положениях — они стоят в трёх различных суммах: вертикаль, горизонталь, диагональ. Середины сторон имеют другое положение — только вертикаль и горизонталь. Это отличает магический квадрат от полумагического — в полумагическом не учитываются диагонали, и углы с серединами имеют равное значение для квадрата.
Сердцевина участвует в четырёх суммированиях — это даёт ей совершенно особую роль, и вы, наверное, это уже заметили.
Раз уж мы коснулись этой темы, в нашем новом квадрате у всех угловых вершин допишем букву у, а у всех не угловых букву с [середина или сторона, как кому удобнее]
Теперь сделаем пару наблюдений. Посмотрите на верхнюю горизонталь и правую вертикаль. У них есть общий угол му. При этом они равны. Для удобства обозначим бс из горизонтали за бс1, а бс из вертикали за бс2. Тогда
бу + бс1 = бс2 + му
бу - му = бс2 - бс1
Очевидно, бу - му положительно. Значит, бс2 - бс1 положительно. То есть бс2 больше, чем бс1.
Теперь посмотрите на диагональ, направленную сверху вниз слева направо и на нижнюю горизонталь. Они тоже равны и у них тоже есть общий элемент. Обозначим верхнее бу за бу1, а нижнее за бу2. Тогда
бу1 + Е = бу2 + мс
Е - мс = бу2 - бу1
Тут тоже видно, что бу2 больше, чем бу1.
Давайте теперь вместо бс2 и бу2 писать Бс и Бу, а вместо бс1 и бу1 по-прежнему писать бс и бу.
Напротив больших Б стоят маленькие м, а напротив маленьких б стоят большие М. Так и будем писать:
В общем-то, мы сейчас с вами получили простейшую модель Бубса и Мумса. Прекрасное название для прекрасной модели. Ей мы и будем пользоваться в дальнейших нуждах, ведь здесь каждый элемент имеет своё собственное название. Но при необходимости, конечно, вернёмся к АВС-модели.
На самом деле, теперь, составляя разные системы равенств и неравенств, мы можем уточнить свои знания о магических квадратах до варианта
Но мы придём к этому другим, очень простым способом.
Но прежде, отмечу, что у Нерегулярного автора есть другая модель, которая, может быть, в чём-то лучше Бубса и Мумса. Он назвал все углы C[corner], все середины S[side], а вместо Е у него M [middle]. Стороны и углы он занумеровал по возрастанию и вышло
S1 < C1 < {S2, C2} < M < {C3, S3} < C4 < S4
К модели Бубса и Мумса я пришёл раньше, но не стану спорить, что она может быть менее эффективной. С другой стороны, обе модели оказываются менее эффективными по сравнению с тем, что я сейчас напишу ниже.
Вообще, будет хорошо, если и БубсМумс и ABC-модели будут у нас перед глазами:
Итак, давайте мы теперь представим, что А больше, чем Е на какое-то полодительное х. Тогда J меньше, чем Е на х. Предположим ещё, что G больше, чем Е на положительное у. Тогда C меньше, чем Е на у. А поскольку у нас
Бу > бу > E, можем уверенно сказать, что
y > x.
Чтобы соответствующие суммы оставались равны 3Е, мы неизбежно введём:
B = E-x+y
D = E-x-y
F = E+x+y
H = E+x-y
Ну всё, теперь просто берём 3 рандомных числа и получаем магический квадрат. Удобно. С учётом того, что x и у положительные, сразу скажем, какие два числа крайние: Бс — самое большое, а мс — самое маленькое. Также понятно, что
E+y > E-x+y и что
E+y > E+x
Остаётся лишь один вопрос — что больше: x или y-x. A или В? бу или бс? Мы никогда не узнаем, потому что может быть и так, и так. Мы можем однозначно указать порядок между всеми числами кроме пар бу-бс и Му-Мс.
Из таких соображений квадраты можно разделить на два вида: те, в которых
2x > y > x и те, в которых
y > 2x
То есть в первом больше верхний угол [18>15], а во втором больше верхняя середина строки [1499>1001].
И можем записать эти квадраты в общем виде на числовой прямой:
Давайте мы также договоримся, что в дальнейшем будем работать лишь с целыми неотрицательными числами. Потому что наше исследование об этом. И тогда все наши штуки будут лежать в промежутке от 0 до 2E. Круто.
Часто в дальнейшем будем использовать НЕМАГИЧЕСКИЙ квадрат следующего вида:
Такой квадрат будем называть порождающим магический. Ну потому что красиво звучит. Типа его отец. Ну потому что переставив элементы мы получим магический. Порождающий удобен тем, что его элементы упорядочены.
Кстати про отцов. Писал как-то код — обход дерева змейкой, и хранил в каждой вершине указатели на следующие элементы дерева: отец, левый брат, правый брат, первый сын, последний сын. Но для обхода змейкой мне пришлось искать элементы правее последнего сына, то есть племянников. В итоге пришлось писать отдельные рекурсивные функции для поиска кузенов, дядей и различного рода пращуров. Я это к чему? Ни к чему, просто захотелось рассказать
Порождающий квадрат Нерегулярный автор в своём исследовании называет интересным. К нему он пришёл раньше меня, но, с другой стороны, эта и подобные штуки определённо очень известны среди тех, кто работал с магическими квадратами 3 на 3.
В общем-то, тут всё. Основную часть статьи я написал, давайте сделаем несколько выводов.
- Любой магический квадрат можно задать с помощью трёх переменных — E, x, y
- Все элементы квадрата можно расставить по порядку. Невозможно определить лишь отношение между двумя соседними элементами больше Е и двумя соседними элементами меньше Е
- Магическая константа любого квадрата — 3Е, а сумма противоположных, или сопряжённых элементов — 2Е.
И ещё пара дополнительных свойств:
— Если прибавить ко всем элементам магического квадрата одно и то же число, полученный квадрат будет магическим
— Если умножить все элементы магического квадрата на одно и то же число, полученный квадрат будет магическим
— Если прибавить ко всем элементам магического квадрата соответствующие элементы другого квадрата, полученный квадрат будет магическим
— Поворот и отражение магического квадрата — магический квадрат.
Как насчёт того чтобы поиграть? То что я пишу ниже, я до сих пор ещё не делал, но оно может оказаться очень полезно.
Раздельчик для любителей экспериментов
Вот я такой любитель алгебры, прочитал свойства магических квадратов и захотел рассмотреть магический квадрат как некоторый объект. Типа матрицы, но с определёнными свойствами.
Так. Пусть М — множество всех магических квадратов, включая те, в которых есть повторяющиеся элементы, нецелые числа и вообще всё что угодно. Ну, то есть, какой-то квадрат, для которого E, x, y — любые вещественные.
В общем виде он выглядит так:
Именно такой квадрат мы будем обозначать как m(E, x, y). Обратите внимание, что если считать повороты и отражения данного квадрата различными с данным, то запись m(E, x, y) задаёт единственный квадрат, и любой квадрат имеет единственную запись m(E, x, y). Тогда нам удобно записывать квадраты в виде m(E, x, y).
Введём операции для квадратов.
- Прибавление к квадрату числа: m(E, x, y)+C = m(E+C, x, y)
2. Умножение квадрата на число: km(E, x, y) = m(kE, kx, ky)
3. Сложение двух квадратов: m(E,x,y)+m(F,u,v) = m(E+F,x+u,y+v)
4. Поворот квадрата по часовой стрелке на 90º: turn(m(E,x,y)) = m(E,y,-x)
5. Транспонирование квадрата: T(m(E,x,y)) = m(E,x,-y)
Конечно, мы можем ввести ещё и какое-нибудь умножение квадратов. Но как нам выгодно умножать квадраты — пока непонятно. Я пока что не работал в таком варианте с квадратами, поэтому не могу ничего об этом сказать. Но что видно уже сейчас: любой квадрат можно разложить как сумму:
m(E, x, y) = m(0, x, 0) + m(0, 0, y) + E
Выглядит чрезвычайно удобно. Я думаю, мы ещё будем этим пользоваться. И как раз давайте рассмотрим эти два нулевых квадрата:
Очень занимательно. В конце концов, всё можно свести и вообще к такому виду:
m(E, x, y) = xm(0, 1, 0) + ym(0, 0, 1) + E
Ну теперь уже точно всё. Заметим только, что если мы всё-таки рассматриваем квадраты, в которых все элементы целые неотрицательные, различные и расставлены по Бубсу и Мумсу, то выполняются два неравенства:
0 < x < y < E;
x+y < E.
Для тех, кто читал статью про яйца и Никит — магические квадраты, можете заметить, составляют коммутативную группу относительно сложения, нейтральным элементом будет квадрат из нулей.
Я придумал ещё одну модель, выглядит она так:
На ней каждая палка означает какой-либо элемент квадрата. Не знаю, можно ли из этой модели вытащить какую-нибудь информацию, но выглядит, определённо, прикольно. Впрочем, она была бы полезнее, рассматривай мы суммы квадратов или произведения.
В общем-то, всё. Всё что нам может пригодиться в будущем, я написал, так что если вы не любите матрицы, можете пролистывать до заключения, а можете и вовсе закрывать эту статью. Есть шанс, что в момент вашего прочтения я уже опубликовал следующие части.
Бонус для любителей линала
А если вы любите матрицы, то тоже не сильно обольщайтесь, ничего сильно интересного я вам не скажу. Просто хотел сказать, что вы, наверное, уже мысленно представили, что магический квадрат это всего лишь матрица с определёнными свойствами, и вам захотелось посчитать её определитель. Сделаем это?
Если кто не понял, что мы делаем — поясню: прибавляем ко второму столбцу первый и третий. Домноженные на единицу, если это имеет для вас значение. Вытаскиваем 3E и прибавляем крайние строки к средней. Выносим 3 и вычитаем третий столбец из первого. Затем первую строку из третьей. Получаем определитель треугольной матрицы и сходу записываем ответ.
Поистине, это лучший из определителей, что мне доводилось находить. Круче было только тогда, когда я засунул треугольник Паскаля в матрицу. Там определитель оказался просто 1.
Отлично, эта статья подошла к концу и она, между прочим, была написана всего за одну ночь. Кажется, у меня стало получаться писать короткие статьи. Сейчас проверю, засуну её в word.
В следующий раз поговорим про не менее замечательную модель НаНакккк, связанную с делимостью.