Магические квадраты

[maxal]

Nataly-Mak писал(а):

Поскольку открытие идеальных квадратов чётно-чётного порядка принадлежит не мне, то прошу кого-нибудь поправить в Википедии то место, где утверждается, что «у идеальных квадратов порядок n>3 и всегда нечётный». Получается, что это совершенно неверно, в той части утверждения, что порядок всегда нечётный. Мне кажется, что утверждение это принадлежит Александрову, им же приведён и идеальный квадрат 9-ого порядка (ссылка дана на его статью). Надо исправить это утверждение и привести пример идеального квадрата восьмого порядка. (статья «Магический квадрат»)

В чем проблема? Исправьте сами...
На приоритет в первооткрывательство каких-либо квадратов тут никто не претендует. Все указанные вам примеры были взяты из открытых источников и представляют собой известные факты.

Nataly-Mak писал(а):

На физико-математическом форуме мне была предложена задача Френикля.
Она состоит вот в чём: требуется превратить нижеследующий магический квадрат
восьмого порядка в пандиагональный перестановкой строк и/или их перевёртыванием
(то есть можно строки переставлять, а некоторые ещё и записывать в обратном порядке).
Или доказать, что сделать это невозможно.
Я составила программу и получила по ней все квадраты, построенные по такой схеме.
Программа выдала 1328 полумагических квадратов и 166 магических.
Пандиагональных среди них не оказалось. Можно ли считать, что задача решена?

Если вы уверены в правильности вашего алгоритма и программы - то да.
Я на всяких случай перепроверил - и пандиагональных тоже не нашел.
А вот магических обнаружил аж 3376 штук.

Nataly-Mak писал(а):

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

Ну я недавно 70-летнего человека основам PARI/GP обучил, возраст - дело наживное.
Но если нет времени или желания постигать новое, то могу порекомендовать UBASIC - этот тот же знакомый вам бейсик, только с поддержкой длинной арифметики и некоторых теоретико-числовых функций, ну и по скорости оптимизированный. С ним переучиваться не придется, а лишь с ознакомиться со списком новых возможностей.

[Nataly-Mak]

Начала строить идеальные квадраты чётно-чётных порядков.
На основе того идеального квадрата восьмого порядка, который мне показали.
Кстати, там, в этой статье, такой квадрат один приведён, или ещё “спрятаны”
где-нибудь? Не понимаю язык. А в Гугле переводить давно уже пробовала, это
такая тарабарщина получается, что ещё меньше понятно, чем на английском.
А идеальные квадраты высших чётно-чётных порядков есть где-нибудь?
Но вернусь к экземпляру идеального квадрата. Испытываю пристрастие к
квадратам, начинающимся с числа 1 (то есть это число стоит в левой верхней
ячейке квадрата). Всегда стараюсь строить именно такие квадраты.
Приведённый экземпляр идеального квадрата восьмого порядка, конечно, можно
сделать начинающимся с числа 1, применив к нему преобразование параллельного
переноса на торе, вот так:

1 48 49 32 25 56 41 8
60 21 12 37 36 13 20 61
4 45 52 29 28 53 44 5
57 24 9 40 33 16 17 64
6 43 54 27 30 51 46 3
63 18 15 34 39 10 23 58
7 42 55 26 31 50 47 2
62 19 14 35 38 11 22 59

Как известно, преобразование параллельного переноса на торе сохраняет
пандиагональность, но нарушает ассоциативность. И теперь квадрат уже не является
идеальным, а только пандиагональным.
Я решила построить идеальные квадраты восьмого порядка, начинающиеся с числа 1.
Прикладываю к схеме, по которой построен показанный мне экземпляр, свой метод качелей,
пишу программу, и она выдаёт мне 36 идеальных квадратов, построенных по этой схеме
и начинающихся с числа 1. Вот один из этих квадратов:

1 32 41 56 49 48 25 8
63 34 23 10 15 18 39 58
4 29 44 53 52 45 28 5
62 35 22 11 14 19 38 59
6 27 46 51 54 43 30 3
60 37 20 13 12 21 36 61
7 26 47 50 55 42 31 2
57 40 17 16 9 24 33 64

Собираюсь написать статью об идеальных квадратах чётно-чётных порядков.
Сейчас попробую построить по аналогичной схеме идеальный квадрат 12-ого порядка.
Хотя пока даже не знаю, существует ли такой квадрат. Кто-нибудь знает?
Кстати, схема, по которой строятся эти квадраты, очень похожа на схему Франклина в
его дьявольски полумагических квадратах. Термин “дьявольски полумагический” принадлежит мне. Я назвала так полумагические квадраты Франклина за их свойство: их можно переносить
на торе и они остаются такими же полумагическими, то есть с такими же суммами по главным диагоналям. О квадратах Франклина см. здесь.
Всё больше убеждаюсь в универсальности метода качелей. С помощью этого метода
я строила: а) полумагические квадраты; б) магические квадраты; в) ассоциативные квадраты
(всех порядков, для которых они существуют);
г) пандиагональные квадраты всех порядков (для которых они существуют);
д) идельные квадраты нечётных порядков.
И вот теперь построила идеальные квадраты чётно-чётного
порядка (пока только для n=8). Разве не универсальный метод? Мне известен
только ещё один такой универсальный метод – это метод построения составных квадратов.
Кто знает ещё такие универсальные методы построения магических квадратов всех видов?

Добавлено спустя 52 минуты 7 секунд:

А знаете, почему у нас получилось разное количество магических квадратов
в задаче Френикля?
Всё очень просто. Когда я говорю о некоторой схеме построения магического квадрата,
то имею в виду незыблемость расположения первых n чисел (n – порядок квадрата).
Это так называемая начальная цепочка. На этом понятии базируется мой метод качелей.
Так вот, наверняка, в ваших магических квадратах есть такие, где схема расположения
первых 8 чисел нарушена, то есть не совпадает со схемой расположения начальной цепочки
в квадрате Френикля. Схема расположения начальной цепочки точно такая же и в квадрате
Агриппа. И я почему-то уверена, что, ставив эту задачу, Френикль хотел получить пандиагональный квадрат именно с такой же начальной цепочкой. Поэтому в алгоритм моей программы и заложена незыблемость начальной цепочки (числа в ней могут переставляться,
но сама схема сохраняется!). Задача Френикля была прочитана тем, кто мне её предложил,
в архиве библиотеки с копий работ Френикля. Поэтому вполне возможно, что он не всё понял
правильно. Я поняла эту задачу именно так. Поэтому у меня так мало получилось
магических квадратов. Но даже у вас пандиагональных квадратов всё равно не получилось.
Вот тот же полумагический квадрат Агриппа 12-ого порядка превращается в магический простой перестановкой строк. Решений получается много, но во всех нарушается схема
расположения начальной цепочки. А это уже не то, что желательно получить.
В этом смысле я говорю, что по схеме Френикля-Агриппа магический квадрат
12-ого порядка не строится (даже с перевёртыванием строк и со смещением чисел в них)
а также и всех порядков n=6k, k=2,4,6… (это гипотеза!)
***
Спасибо за рекомендованный язык. Я обязательно посмотрю. А для него тоже нужен
интерпретатор?

[Nataly-Mak]

Вижу, статью в Википедии поправили. Хорошо.
Кто-нибудь нашёл идеальный квадрат 12-ого порядка?
Я построила два частных решения по аналогии с идеальными квадратами
восьмого порядка (частные решения строятся без программы).
И получила очень интересные экземпляры. Когда я строила идеальные
квадраты нечётных порядков, встречала подобные квадраты и назвала их
псевдоидеальными. Эти квадраты ассоциативны. Суммы по главным и
разломанным диагоналям равны магической константе квадрата. Нет только
магических сумм в строках и столбцах. Приведу один такой квадрат:

1 48 61 96 109 132 121 120 85 72 37 12
143 98 83 50 35 14 23 26 59 74 107 134
4 45 64 93 112 129 124 117 88 69 40 9
142 99 82 51 34 15 22 27 58 75 106 135
6 43 66 91 114 127 126 115 90 67 42 7
140 101 80 53 32 17 20 29 56 77 104 137
8 41 68 89 116 125 128 113 92 65 44 5
138 103 78 55 30 19 18 31 54 79 102 139
10 39 70 87 118 123 130 111 94 63 46 3
136 105 76 57 28 21 16 33 52 81 100 141
11 38 71 86 119 122 131 110 95 62 47 2
133 108 73 60 25 24 13 36 49 84 97 144

Суммы в строках этого квадрата имеют такие значения: 894 и 846, в строгом
чередовании, а суммы в столбцах – 872 и 868 и тоже чередуются. Если не обратить
внимания на суммы в строках и столбцах, то можно принять этот квадрат за идеальный.
Итак, с частными решениями не получилось. Надо писать программу и искать
все решения, возможно, и найдётся среди всех решений идеальный квадрат.
Если кто нашёл идеальный квадрат 12-ого и высших чётно-чётных порядков,
дайте, пожалуйста, ссылку. А может, кто-нибудь сам построит такие квадраты?
Подключайтесь!

[TOTAL]

Nataly-Mak писал(а):

А может, кто-нибудь сам построит такие квадраты? Подключайтесь!

Существуют ли задачи с магическими квадратами, которые (задачи) можно решать в уме?

[maxal]

В уме неинтересно. Лучше уж сразу браться за нерешенные задачи - типа тех, что перечислены здесь:
http://www.multimagie.com/English/Problems.htm

Я сейчас пробую найти нетрадиционный би-магический квадрат 5x5. Если хватит вычислительных ресурсов, я его либо найду, либо докажу, что его нет

Другая интересная задача - найти нетрадиционный магический квадрат 3x3, состоящий из различных точных квадратов. Предложена Мартином Гарднером еще в 1996, до сих пор не решена. Сам Гарднер назначил за нее приз в $100, и аналогичный приз уже назначен за всего лишь подзадачу этой задачи (подробности см. по ссылке).
У этой задачи есть красивая формулировка в терминах эллиптических кривых, нужно будет пожалуй обсудить в соответствующей теме...

[Nataly-Mak]

Ну как, доказали, что би-магического квадрата 5-ого порядка не существует?
А что, разве это ещё никто не доказал?
У меня вроде просто получилось.
Сначала я написала маленькую программку, которая выдала мне все строки магических
квадратов 5х5, способные превратиться в би-магические строки, то есть сумма квадратов
чисел в этих строках равна 1105.
Массив таких строк оказался не таким уж и большим. Вот начало этого массива:

1 10 14 18 22
2 8 14 20 21
2 10 13 16 24
4 5 16 18 22
4 6 13 20 22
4 8 10 21 22

Могу показать и весь массив.
Ну, а дальше решала задачу, что называется, в уме. Из строк этого массива попыталась
составить хоть один магический квадрат 5х5. И это у меня не получилось.
Не составляется ни один такой квадрат из этих строк!
Вот такое моё доказательство. Годится?
***
Начала писать статью “Идеальные квадраты чётно-чётного порядка”.

[maxal]

Nataly-Mak, доказательство-то годится, но для другой задачи. Я упустил слово "нетрадиционный" в ее описании (уже исправлено!), то есть числа в этом квадрате могут быть совсем не обязательно от 1 до 25, а произвольные различные. А моя программа все считает, не такое это простое дело отыскать оный квадратик...

[Nataly-Mak]

Цитата из статьи по приведённой вами ссылке:

«Что является самым маленьким bimagic квадратных использованием различных чисел? Ее размер неизвестен: 5x5, 6x6 или 7x7? Мое мнение состоит в том, что 5x5 bimagic квадратов не существует. Bimagic квадратов размером 8x8 и выше, уже известны. Не решена, но сначала 6x6 bimagic квадратов путем Ярослав Вроблевский в 2006 году, сначала 7x7 bimagic квадратов Ли Моргенштерн в 2006 году. 5x5 still unknown. 5x5 сих пор неизвестна».
(переведено в Гугле)

Итак, речь идёт о нетрадиционных bimagic квадратах, заполняемых различными числами.
Если такой квадрат 5х5 существует, возможно, вы его вычислите. Но вряд ли вам удастся
доказать, что его не существует. Натуральный ряд чисел бесконечен. Никаких вычислительных
ресурсов вам не хватит, чтобы просчитать этот ряд чисел до конца, потому что конца-то
нет. Только традиционных магических квадратов пятого порядка существует несколько
миллионов. Что же говорить о нетрадиционных! Их количество даже оценить нельзя
(как я понимаю).
То есть доказывать надо не в лоб, вычисляя все матрицы, заполненные точными
квадратами натуральных чисел (да притом, что сами эти числа
составляют нетрадиционный магический квадрат пятого порядка), а каким-то другим путём.

[maxal]

Nataly-Mak, вы все правильно говорите, но вот почему вы решили, что я "в лоб вычисляю все матрицы, заполненные точными квадратами натуральных чисел"? Я конечно, косвенно вычисляю их, но отнюдь не в лоб.

Как и обычные квадраты, би-магические представляют собой решения некоторой системы уравнений. Но в отличие от обычного случая, где все уравнения линейные, в случае би-магических квадратов часть уравнений является квадратными. Системы линейных уравнений, конечно, гораздо лучше изучены, и их можно очень быстро решать, как впрочем и однозначно определять случаи, когда система уравнений не имеет решений (правило Крамера и т.п.). Но и у систем квадратных (и даже более общих: полиномиальных) уравнений тоже есть методы решения. То есть, существует процедура (алгоритм), которая за конечное время либо приведет к решению, либо докажет, что решений нет. Единственное препятствие на этом пути - она не такая эффективная, как хотелось бы, и пресловутое "конечное время" может оказаться очень большим.

Таким образом, у вычислений, которые я сейчас провожу, может быть несколько исходов: 1) я найду искомый би-магический квадрат; 2) я докажу, что его не существует; 3) время вычислений превысит разумные пределы, и я рано или поздно брошу это занятие, так ничего и не найдя, и не доказав; 4) случится сбой в компьютере или программе (в том числе, например, если расход памяти превысит доступным объем), и вычисления будут прерваны по независящей от меня причины. Трудно прогнозировать, что конкретно случится, но я надеюсь на первые варианта.

[Nataly-Mak]

О нетрадиционном квадрате 3х3, заполненном точными квадратами.
Эта задача, как мне кажется, решается очень просто в лоб.
Программа пишется элементарно. Например, так:

10 DIM A(1000), B(9)
17 FOR X = 1 TO 1000: A(X) = X * X: NEXT X
20 FOR I = 1 TO 1000
25 FOR J = 1 TO 1000
30 IF J = I THEN 520
35 FOR K = 1 TO 1000
40 IF K <> I THEN IF K <> J THEN 44
42 GOTO 515
44 B(1) = A(I): B(2) = A(J): B(3) = A(K)
46 Z1 = B(1) + B(2) + B(3)
48 FOR L = 1 TO 1000
50 IF L <> I THEN IF L <> J THEN IF L <> K THEN 54
52 GOTO 510
54 B(5) = A(L)
56 B(8) = Z1 - B(2) - B(5)
58 IF B(8) > 0 THEN 62
60 GOTO 510
62 Z2 = SQR(B(8))
64 IF Z2 = INT(Z2) THEN 68
66 GOTO 510
68 B(9) = Z1 - B(1) - B(5)
70 IF B(9) > 0 THEN 74
72 GOTO 510
74 B(6) = Z1 - B(3) - B(9)
76 IF B(6) > 0 THEN 80
78 GOTO 510
80 Z2 = SQR(B(6))
82 IF INT(Z2) = Z2 THEN 86
84 GOTO 510
86 B(7) = Z1 - B(3) - B(5)
88 IF B(7) > 0 THEN 92
90 GOTO 510
92 Z2 = SQR(B(7))
94 IF INT(Z2) = Z2 THEN 98
96 GOTO 510
98 IF B(7) + B(8) + B(9) <> Z1 THEN 510
100 B(4) = Z1 - B(1) - B(7)
102 IF B(4) > 0 THEN 106
104 GOTO 510
106 IF B(4) + B(5) + B(6) <> Z1 THEN 510
108 FOR X = 1 TO 9
110 PRINT B(X);
112 NEXT X
114 PRINT "KVADRAT POSTROEN!"
116 GOTO 530
510 NEXT L
515 NEXT K
520 NEXT J
525 NEXT I
530 END

Искусственно задав в этой программе значения переменных I=373, J=289, K=565, L=425,
я получила на выходе магический квадрат, приведённый по указанной ссылке, то есть
нетрадиционный магический квадрат 3х3, в котором 7 точных квадратов. Вот такой:
B(1)=139129 B(2)=83521 B(3)=319225 B(4)=360721 B(5)=180625 B(6)=529
B(7)=42025 B(8)=277729 B(9)=222121
Если есть ещё такие матрицы (с 7 точными квадратами) в пределах первых 1000
натуральных чисел, то по этой программе они будут найдены.
Далее надо вставить в программу условие, что ещё одно число в матрице является
точным квадратом, и искать матрицы с 8 точными квадратами. А затем и с 9.
Ну, и следующий этап – расширение массива чисел.
Только как выполнить такую программу? Для меня это нереально.
Кто-нибудь может выполнить?
Перепишите программу на другом языке (с хорошим быстродействием) и попробуйте
выполнить. Сразу вставьте условие, что ещё одно число в матрице является точным квадратом.
Если есть такой квадрат в пределах массива из 1000 чисел, вы его обязательно вычислите.
Но наверное всё-таки выполнить такую программу нереально? А?

Добавлено спустя 12 минут 54 секунды:

Ну, описание магических квадратов с помощью систем уравнений мне известно.
Сама использовала этот приём, когда искала все 144 пандиагональных квадрата
пятого порядка.
И что: вы надеетесь найти все решения такой системы уравнений в натуральных
числах? Сомневаюсь, что вам это удастся. Опять же: поскольку натуральных чисел
бесконечно много, то и решений будет бесконечно много. И как же их все найти?

[maxal]

Nataly-Mak, программный код нужно заключать в тэги [code] ... [ /code]. Отредактируйте свое сообщение, нажав кнопку !

[Nataly-Mak]

Если вы составили систему уравнений, однозначно определяющую би-магический
квадрат 5х5, то попробуйте доказать, что такая система не имеет решений в натуральных числах.
И ничего не надо вычислять!

[maxal]

Nataly-Mak писал(а):

И что: вы надеетесь найти все решения такой системы уравнений в натуральных числах? Сомневаюсь, что вам это удастся. Опять же: поскольку натуральных чисел бесконечно много, то и решений будет бесконечно много. И как же их все найти?

Ну во-первых, все решения меня пока не интересуют - для начала нужно найти хотя бы одно. А там посмотрим.
А во-вторых, ниоткуда не следует, что решений будет бесконечно много. Априорно возможен любой из вариантов: нет решений, конечное число решений или бесконечное число решений.

Nataly-Mak писал(а):

Если вы составили систему уравнений, однозначно определяющую би-магический квадрат 5х5, то попробуйте доказать, что такая система не имеет решений в натуральных числах. И ничего не надо вычислять!

С чего вы взяли, что это можно проделать безо всяких вычислений? Кроме того, как я уже говорил, существующие алгоритмы потенциально могут доказать, что подобная система уравнений не имеет решений. Поэтому я не вижу смысла возится с пресловутой системой самому, пока не будет понятен исход ее компьютерного решения. Если оно так или иначе обломится, будем думать, что делать дальше.

[Nataly-Mak]

Я не совсем точно выразилась: конечно, система, описывающая нетрадиционный
би-магический квадрат 5х5, вряд ли будет иметь бесконечно много решений.
Хотя бы одно имела!
Имелось в виду, что имеется бесконечно много кандидатов в решения, и их все надо
проверять, будут ли они действительно решениями. А вот это сделать как раз и
невозможно, то есть проверить всех кандидатов.
Конечно, чтобы доказать, что система не имеет решения, тоже кое-что придётся
вычислять (виновата, опять не совсем точно выразилась)
Например, для систем линейных уравнений достаточно вычислить определители системы.
Но не столь же много вычислять.
***
В этой статье
http://www.geocities.com/~harveyh/franklin.htm
приведён магический круг Франклина и говорится, что якобы в этом круге заложен
некий алгоритм построения магических (или полумагических) квадратов.
Сколько я ни смотрела на этот круг, никакого алгоритма увидеть не смогла.
Может быть, кто-нибудь увидит этот алгоритм?

[Nataly-Mak]

Цитата:
«В науке, как и в любом виде творчества, встречается негативное явление, называемое плагиатом. Мне, популяризатору математических знаний, часто приходится сталкиваться с недобросовестными исследователями, полностью копирующими результаты других авторов. Приведу только один пример – поиск идеальных магических квадратов.
Идеальный магический квадрат представляет собой квадратную матрицу n × n ( n – нечетное число, за исключением единицы и тройки ), заполненную числами от 1 до n2 таким образом, что:
1) сумма чисел в каждой строке равна Mn;
2) сумма чисел в каждом столбце равна Mn;
3) сумма чисел в каждой главное диагонали равна Mn;
4) сумма чисел в каждой разорванной диагонали равна Mn .
5) сумма двух любых центрально противолежащих чисел одинакова и равна 1 + n2.
То есть, идеальные магические квадраты – это одновременно пандиагональные (или дьявольские) квадраты и ассоциативные магические квадраты.
Здесь Mn – магическая сумма, равная 0,5 • n • ( 1+n2 ).
Данную задачу пытались решить в начале 20-го столетия A.Margossian (Франция) и J.R. Hendricks (Канада). Но им не удалось найти идеальные магические квадраты, у которых нечетный порядок n кратен трем. Максимальное, чего они добились – это получить пандиагональные квадраты 9×9, 15×15 и 21×21.
Впервые строгий алгоритм компоновки идеальных магических квадратов для любых нечетных n > 3 разработал лишь в конце 2007 года москвич Г.Александров http://renuar911.narod.ru/IMSb.html, http://renuar911.narod.ru/IMS-D.html»

Это цитата из статьи «Плагиат в науке»
http://gromov7043.narod.ru/plagiat.html

Автор статьи Николай Громов выдвигает в этой статье обвинения в плагиате в мой адрес. То есть на основании того, что я своим методом качелей построила точно такой же квадрат (я в статье специально подчеркнула, что составленная мной программа выдаёт
среди прочих решений и квадраты, полученные Александровым), какой построил Александров, Громов делает вывод, что я просто “срисовала” квадрат Александрова. То, что я построила методом качелей сотни других идеальных и пандиагональных квадратов самых разных порядков, которые не построил Александров (и его методом некоторые из построенных мной квадратов построить просто невозможно!), автор почему-то не заметил.
Конечно, я ничуть не расстроилась от такого обвинения, потому что знаю, что ничего ни у кого не “срисовывала”, а всё действительно построила сама разработанным мной методом качелей, который, кстати сказать, оказался универсальным методом.
Если бы действительно была плагиатором, не стала бы публиковать это сообщение.
Привожу эту цитату потому, что этот горе-популяризатор математических знаний до сих пор пребывает в уверенности, что идеальные квадраты существуют только нечётных порядков.
А я, между прочим, сегодня построила идеальные квадраты 40-ого порядка.
Смотрите статью “Идеальные квадраты чётно-чётного порядка”.
У меня возник такой вопрос: в нетрадиционном би-магическом квадрате обязательно должно присутствовать число 1? В приведённом по указанной здесь ссылке нетрадиционном би-магическом квадрате 6-ого порядка число 1 присутствует.
Если присутствие числа 1 необязательно (как и вообще в любом нетрадиционном квадрате), то у меня интересный момент обнаружился.