MagicSquare2. Модель НаНакккк. Квадратные квадраты
Всем привет, я Мынка, мы говорим про магические квадраты, и вы, кстати, тоже.
Если вы не читали прошлую статью из этой темы, я обиделся, ведь прежде чем перейти к новому разделу исследования, я бы хотел обсудить то, к чему мы в прошлый раз.
Мы ввели алгебраический объект — магический квадрат, и несколько свойств для него. Хорошенько подумав об этом, я понял, что все введённые нами свойства — это свойства матриц. То есть мы можем задать магический квадрат как особую матрицу. Если вы с ними не знакомы, то никаких проблем нет, матрица это просто табличка с циферками, которая складывается примерно так же, как мы складывали квадраты. Если знакомы, что вероятно, то следующий кусочек, не требующий, однако, глубокого знания, — для вас.
СЛАБОНЕРВНЫМ ПРОЛИСТАТЬ!
Магический квадрат как матрица.
Очевидно, матрицы m(1,0,0), m(0,1,0), m(0,0,1) — магические квадраты:
При этом любой другой квадрат — это матрица-сумма этих трёх матриц, умноженных на коэффициенты.
m(E,x,y) = Em(1,0,0) + xm(0,1,0) + ym(0,0,1)
Красиво, хотя мы уже это видели раньше.
Как мы уже отмечали, квадраты образуют абелеву группу относительно сложения. Всё понятно. Мы же, как любители матриц, хотим узнать, что же получится при перемножении двух квадратов. Я не поленился и умножил m(E,X,Y) на m(e,x,y). Вот что из этого вышло:
Это, безусловно, не магический квадрат, но что-то очень интересное. Исследовать эту штуку мы, правда, не будем. Оставлю это вам, если хотите.
Определитель мы с вами уже считали. Он равен, как вы можете помнить,
9E(y²-x²).
На самом деле, не лучшее, что можно было получить, с учётом того, что x и у находятся в равных положениях, если не вводить уточнение y > x. И разность здесь не очень понятна. С другой стороны, это же определитель, наверное, ничего странного.
Ладно, больше мы не получим ничего интересного, поэтому перейдём к теме.
Исследование магических квадратов через делимости
В процессе вычислений мы будем использовать модульную арифметику. Вообще, мы уже использовали её в статье про яйца и Никит, но на всякий случай повторюсь, запись
Означает, что у a и b одинаковые остатки при делении на с. И там дальше куча свойств. Не мне вам их рассказывать, я их буду просто использовать, а вы будете смотреть и думать: «ого, так что ли можно??»
Ещё раз продублирую квадрат, для удобства:
Хорошо. Начнём с такого простого факта: пусть E делится на какое-то простое число p. Тогда и магическая константа тоже делится на p. Тогда если какой-то элемент делится на p, то и сопряжённый с ним тоже делится на p и наоборот: если один не делится, то и другой не делится. Круто. То есть количество не делящихся на p элементов всегда чётно.
В таком случае, возможны 5 ситуаций:
- На p делятся все элементы. В таком случае, мы можем вынести общий множитель за знак квадрата и получить другой магический квадрат. Поэтому такой случай нас не интересует.
- На p не делится 2 элемента.
- На p не делится 4 элемента.
- На p не делится 6 элементов.
- На р не делится 8 элементов.
В общем-то, те, что не делятся, я отмечал в своём исследовании как На и на, но я забыл, почему а, поэтому вместо элементов мы будем писать остаток от деления на p. Кратные я обозначал буквой к, отсюда название модели — НаНакккк. Название оставим, потому что оно туяуаок, но использовать будем более эффективные методы.
Итак, p — делитель Е. Поэтому грубо, но запишем так:
Будем считать, что два квадрата сравнимы по модулю в том случае, когда сравнимы по модулю все их элементы. Я считаю, вполне нормально.
Итак, мы будем рассматривать квадрат m(0, x, y):
Важно: существование квадрата остатков является необходимым условием существованием самого магического квадрата. Если квадрат остатков не существует, то не существует и магический. Если квадрат остатков существует, то мы не можем ничего сказать о магическом.
Думаю, понятно. В каких ситуациях у нас есть элементы, кратные p? Таких ситуаций четыре:
То есть у всех квадратов с 6-ю некратными p элементами есть шансы на существование. Круто. Теперь попробуем скомбинировать.
Заметим, что если выполняется первое и какое-то ещё, то выполняются сразу все. Если выполняется второе и какое-то ещё, то тоже выполняются все сразу. Если выполняются одновременно третье и какое-то ещё, то тоже выполняются все сразу!
Да… Почти так, но есть маленькое, совсем мулипусенькое исключение. Если
p = 2, то третье и четвёртое могут выполняться без первого и второго. Надеюсь, объяснять не нужно, почему. Если два числа имеют одинаковую чётность, то и их разность, и их сумма чётна. Так не работает ни с одним числом кроме 2.
Но. С двойкой всё вообще сложно. Если Е делится на 2, то как минимум два других элемента делятся на 2. Иначе у вас просто не выйдет магический квадрат прям совсем никак. Можете доказать по тем четырём выражениям выше.
Поэтому вывод:
— Если у Е есть какой-то простой делитель p, отличный от двух, и не все элементы квадрата делятся на p, то либо все остальные элементы не делятся на p, либо делятся только два из них, и они сопряжены.
— Если Е делится на 2, то может быть либо два, либо четыре кратных p делителя, тогда все они стоят на средней вертикали и средней горизонтали.
Как-то быстро у меня закончился материал для статьи. Это обидно. Из-за того что статья получается такой маленькой, мне уже сейчас придётся сделать переход к основной части исследования. А я не хочу, я собирался это сделать в следующей части.
Ну ладно, так и быть. Давайте расскажу, зачем нам НаНакккк.
Действительно, зачем нам НаНакккк? Это нужно в том случае, когда вам дают 9 чисел и спрашивают: а можно? А вы такие: что можно? А вам говорят: построить магический квадрат из них? А вы им: ну вот вы мне дали 9 чисел, выбираем из них среднее — оно делится на 5. Кроме него на 5 делится ещё 4 числа, а так нельзя, идите-ка вы в жопу.
Так оно работает. Как правило, определить несуществование квадрата по делимостям для человека проще, чем как-то иначе. А как иначе? Взять средний элемент, вычесть его из всех прочих. Должны получиться 4 пары противоположных элементов, причём элементы из двух пар равны сумме и разности элементов других пар. В общем, вот. Думайте теперь об этом.
Как было сказано в первой статье — наша цель: собрать информацию о магическом квадрате, состоящем из квадратных чисел. То есть о таком:
До сих пор такой квадрат не был найден, не доказано, что он не существует и не сильно понятно, как его искать при современных мощностях компьютеров. Поэтому нам с вами не остаётся ничего кроме как рассматривать его математически. Самое главное, что мы не можем сделать — записать этот квадрат в виде полюбившейся нам функции m(E,x,y), ведь квадрат из квадратов это нечто совсем иное, его нельзя расписать на сумму других квадратов, чтобы это что-то дало.
Тем не менее, здесь мы всё ещё можем использовать модели Бубса и Мумса, НаНакккк, а ещё можем накапливать другие знания.
Но сегодня мы говорим про делимости, поэтому давайте посмотрим, что изменится, если мы введём квадраты.
Если Е² делится на p, то оно делится и на p². То есть если Е чётное, то Е² делится на 4. Значит, суммы A²+J², B²+H², C²+G², D²+F² должны делиться на 4. Это невозможно в том случае, если хотя бы одно из этих чисел нечётно, ведь все квадраты имеют остаток от деления на 4 либо 0, либо 1. Выходит, все эти числа делятся на 4. Но тогда все элементы квадрата делятся на 4, и мы можем вынести 4 за квадрат, получив другой квадратный квадрат. Поэтому нам имеет смысл рассматривать лишь те квадраты, в которых все числа нечётные. Это, безусловно, плюс.
Теперь зайдём по-другому. Предположим, что числа ABCDFGHJ отдалены от Е на abcdfghj. Это не тупые наборы букв, это мне лень ставить запятые.
С учётом Бубса и Мумса, можем сразу расставить плюсы и минусы так, чтобы все числа abcdfghj были положительными:
При этом, в известных нам обозначениях
Поработаем с первым уравнением:
Теперь давайте рассуждать. Из-за того что у нас в квадрате все числа нечётные, мы можем сразу сказать, что a и j чётные, ведь это разности между А и Е и Е и J. Если они оба чётные, то введём временную замену:
Теперь мы очень хотим избавиться от m — n в знаменателе. Оно нас бесит, ведь в числителе стоит 2mn. Неприятно как-то. Чтобы однозначно установить, что на что делится, нам нужно ввести ещё замен.
То есть x — это собственная часть m, а вместе с тем и j, а y — это собственная часть n. Если x и у не имеют общих делителей, то и x-y не имеет ни с одним из них общих делителей [этот простой факт я позволю вам доказать самостоятельно]. Значит, неизбежно 2k должно делиться на x-y.
Продолжим вводить замены? Уберём из выражения иксы.
В данной ситуации чётными могут оказаться l, так и z, а может и всё вместе. Главное, что что-то одно чётное. Теперь мы можем остановиться. Вот три параметра — l, y, z, через которые мы можем без проблем задать Е. Более того, теперь мы через эти три параметра сможем задать A и J:
Ну давайте себя проверим. Возьмём три рандомных числа и подставим вместо l, y, z. Важно: либо l, либо z чётно, y — любое. Ну, например, l = 3, y = 7, z = 2. Тогда:
И остаётся проверить, что сумма их квадратов равна 3E²:
Как видите, работает. Можете догадаться, что впредь нам придётся работать с очень большими числами. На красивенький квадратик из циферок 123456789 можете не рассчитывать.
Вспомним про то, что Е нечётное и добавим условия:
— l и z не могут быть чётными одновременно
— z и y не могут быть чётными одновременно
— l не может делиться на 4
Ну и ещё мы можем выразить А и J через l, y, z напрямую, не используя E:
Давайте теперь обратим внимание, что l или l/2 при нечётном z — это общий делитель чисел E, A, J.
Внимание также обратим на то, что, на самом деле, выполняются все следующие 4 системы:
Если для вас это не очевидно, посмотрите ещё раз сюда:
и вспомните, как мы получили первую систему.
Итак, теперь возвращаемся к НаНакккк. Если сейчас мы посмотрим на эти системы, то увидим, что E делится на все числа l1, l2, l3, l4 [или на них же, делённых на 2, если соответствующие z нечётны]. А каждая пара чисел AJ, BH, CG, DF делится на соответствующее ей l [возможно, делённое на 2]. Мы знаем, что если Е делится на какое-то число p, то на него может делиться только одна пара других элементов. Отсюда следует, что все числа l1, l2, l3, l4, делённые на 2— взаимно простые.
Отсюда, в свою очередь, могло следовать, что у Е должно быть как минимум 4 различных делителя, но не следует, потому что все эльки вполне могут быть равны одному или двум.
Тем не менее, к делителям Е мы ещё придём. Пока я обойду эту тему стороной, она большая, у нас уйдёт на неё целая статья.
А сейчас обсудим ещё один момент и будем заканчивать, наверное. Выбирая три разных числа l, y, z, мы можем получать три числа А, Е, J, необходимые нам в квадрате. Так вот числа A, E, J будем называть триплетом. И любые три числа, такие, что сумма их квадратов равна магической константе, то есть 3E². А те триплеты, в которые входит E будем называть еплетами [потому что звучит крайне хорошо]. То есть A, E, J — еплет.
Мы с вами прекрасно умеем получать еплеты, мы даже вывели для них параметрическую зависимость [от l, x, y], но на деле пользоваться этой зависимостью не очень удобно. Потому что никогда непонятно, что в результате будет.
Чтобы искать квадрат в дальнейшем, мы будем перебирать Е. То есть Е нам известно. Поэтому нам удобнее выражать не Е через параметры, а параметры через Е. Ну хотя бы один из параметров выразить через Е и другие параметры. Давайте так:
Стопстопстопстопстоп. Здесь остановимся. Вот это я мудило. Я ввёл выше две замены, и замена z, как вы видите, оказалась, безусловно, лишней.
Нам намного удобнее здесь работать с иксом. То есть убираем z, возвращаем x:
Вау! Я правда мудило, не заметил такую красивую вещь.
У нас с вами x и y используются в двух разных местах в разных смыслах, давайте здесь мы будем писать не x и y, а u и v:
Тогда z = u-v, y = v+z. Давайте тогда ещё выразим А и J теперь:
И ещё раз выпишем итоговые формулы, чтобы были перед глазами:
Проверим: l = 1, u = 5, v = 3:
Всё, хорошо, идём дальше. Как я сказал, чаще нам известна Е, чем какие-то левые параметры. Поэтому выразим l/2 через Е и подставим во все остальные выражения:
И появляется ощущение, что мы ходим по кругу. Но вообще-то нет. Мы просто не можем взять такие u и v, что Е не делится на u²+v².
Теперь обратите внимание на то, что если u и v не равны и положительны [а так и есть, ведь иначе А = Е = J, что нарушает нашу договорённость о том, что в квадрате все числа различны], то сумма их квадратов — какое-то число, которое хорошенько портит нам жизнь, находясь в знаменателе. Е должна обязательно делиться на эту сумму квадратов, а поскольку кроме AJ у нас есть ещё BH, CG и DF, и у каждого из них тоже есть сумма квадратов, выходить, Е должна делиться как минимум на 4 суммы квадратов. Да?
Я вас очень круто обманул, надеюсь, вы не заметили. Предлагаю вам самим найти логическую ошибку в абзаце выше.
Тем не менее, Е действительно должна делиться, пусть и не на четыре, но как минимум на две суммы квадратов. Этот факт мы будем доказывать в следующей статье. К сожалению, к нему Нерегулярный автор пришёл раньше меня, но этот факт является ключевым, так что я не могу о нём не рассказать.
Мы доказывали его через гауссовы целые числа. Думаю, мы с вами сможем доказать его простой математической индукцией, но вам маленькое домашнее задание к следующей статье:
- Доказать, что любое простое вида 4k+3 не представимо в виде суммы двух квадратов
- Доказать, что любое простое вида 4k+2 представимо в виде суммы двух квадратов единственным образом [задача с подвохом]
- Доказать, что любое простое вида 4k+1 представимо в виде суммы двух квадратов единственным образом [задача без подвоха]
- Доказать, что любое простое вида 4k одновременно представимо в виде суммы двух квадратов и не представимо в виде суммы двух квадратов
Делать это домашнее задание не обязательно, но вам должно быть весело.
Ещё можете прочитать статью про секреты индусов [хотя там уместнее всё же греки] и в статье про яйца и Никит кусочек про комплексные и гауссовы числа. Они нам, к сожалению, пригодятся.
А сегодня всё. Желаю, чтобы в вашей жизни всё было Бубс-Мумс и НаНакккк.