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

[tolstopuz]

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

Как-то всё очень туманно!

Попробуйте приписать к своему рис. 1 слева столбец с единицами, а потом снизу строку $(x_1, x_2, x_3, x_4, 1, \ldots, 1)$.

У меня получилось вот что:

15 17 14  7 10  8  5 16 13  3  6  4 12 18  1 11  9  2
18 15 17  1  8 11  9  6 16 14  4  7  5 13  2 12 10  3
14 18 15 17  2  9 12 10  7 16  1  5  8  6  3 13 11  4
 7  1 18 15 17  3 10 13 11  8 16  2  6  9  4 14 12  5
10  8  2 18 15 17  4 11 14 12  9 16  3  7  5  1 13  6
 8 11  9  3 18 15 17  5 12  1 13 10 16  4  6  2 14  7
 5  9 12 10  4 18 15 17  6 13  2 14 11 16  7  3  1  8
16  6 10 13 11  5 18 15 17  7 14  3  1 12  8  4  2  9
13 16  7 11 14 12  6 18 15 17  8  1  4  2  9  5  3 10
 3 14 16  8 12  1 13  7 18 15 17  9  2  5 10  6  4 11
 6  4  1 16  9 13  2 14  8 18 15 17 10  3 11  7  5 12
 4  7  5  2 16 10 14  3  1  9 18 15 17 11 12  8  6 13
12  5  8  6  3 16 11  1  4  2 10 18 15 17 13  9  7 14
17 13  6  9  7  4 16 12  2  5  3 11 18 15 14 10  8  1
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
11 12 13 14  1  2  3  4  5  6  7  8  9 10 16 15 18 17
 9 10 11 12 13 14  1  2  3  4  5  6  7  8 17 18 15 16
 2  3  4  5  6  7  8  9 10 11 12 13 14  1 18 17 16 15

[maxal]

Nataly-Mak в сообщении #190970 писал(а):

Общий ход вашего доказательства мне понятен. Впрочем, общая идея, совпадающая с вашей, была высказана Эйлером (см. цитату выше). Однако приведённую вами схему доказательства нельзя считать строгим доказательством.

А я и не утверждал, что это строгое доказательство - я всего лишь набросал в общих чертах алгоритм практического решения задачи.
Более того, я думаю, что в общем виде это утверждение неверно - хотя для большинства квадратов оно работает, можно придумать пример, для которого это не так.
Однако, в MOLS возможна еще одна операция - одновременная перестановка строк/столбцов во всех квадратах образующих MOLS. С помощью таких операций можно существенно изменить содержимое диагоналей, и даже если они были "плохими" (в указанном выше смысле), то их скорее всего их можно превратить в "хорошие", а дальше уже составлять и решать систему для последующего переобозначения.

[Nataly-Mak]

maxal писал(а):

Более того, я думаю, что в общем виде это утверждение неверно - хотя для большинства квадратов оно работает, можно придумать пример, для которого это не так.

Во-первых, приведённая вами цитата принадлежит мне, а не пользователю tolstopuz.
Вы можете придумать пример, опровергающий мою гипотезу? Или вы только предполагаете, что она неверна? Так я же и прошу: либо доказать утверждение, либо опровергнуть его. Приведите опровергающий пример!
Я же не просила приводить алгоритм практического решения задачи, потому что практически задача рашается элементарно: выписываются числа неправильной диагонали, считается сумма чисел в этой диагонали и простым подбором находится замена. Не надо огород городить, составлять и решать системы уравнений. Именно так я преобразовала множество недиагональных латинских квадратов. Вот простой пример: неправильная диагональ в латинском квадрате 18-го порядка:
3 14 6 3 10 14 18 16 13 2 6 3 7 18 12 8 6 7
Сумма чисел в строках и в столбцах латинского квадрата 18-го порядка равна 171, сумма чисел в приведённой диагонали равна 166. Очевидно, что всего одна замена - числа 10 на число 15 - даёт нужную сумму чисел в этой диагонали. Разумеется, чтобы во всём квадрате все суммы чисел сохранились, надо выполнить и взаимную замену - числа 15 на число 10.
Уверена в том, что моё утверждение (которое в сущности было проверено Эйлером для латинских квадратов 3х3, 4х4 и 5х5, как утверждается в приведённой выше цитате) верно для пары ОЛК любого порядка, удовлетворяющей условиям, сформулированным мной в постановке задачи. Жду опровергающий пример!
Насчёт операции перестановки строк и/или столбцов. Эта операция тоже рассматривается в цикле статей "Новые аспекты метода латинских квадратов". Однако это тоже надо доказать: что любой греко-латинский квадрат можно превратить в магический квадрат перестановкой строк и/или столбцов. Несколько частных примеров такого превращения приведено в моих статьях. Вы можете доказать, что это верно для греко-латинского квадрата любого порядка?

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

tolstopuz
Спасибо вам за третий квадратик! Я его проверила, он действительно ортогонален двум построенным мной. Но как вы додумались до прибавления таких столбца и строки?
Посмотрите, пожалуйста, на следующую матрицу (автор Wojtas):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 10 4 14 8 18 2 12 16 6 11 1 15 5 19 9 13 3 7 17
0 11 17 6 12 3 9 18 14 5 1 10 16 7 13 2 8 19 15 4
0 3 12 8 15 1 19 4 5 10 14 18 17 11 9 7 2 16 6 13

В статье вроде говорится, что по этой матрице можно построить группу MOLS 20-го порядка, состоящую из 4 квадратов. У меня ничего не получается! Что надо к этой матрице добавить? Прямо сполошные загадки
Ещё очень интересно познакомиться с методом построения групп MOLS, основанным на полях Галуа. Не могли бы вы показать конкретный пример?
Если есть время, посмотрите, пожалуйста, на пару ОЛК 18-го порядка, построенную мной ранее ( http://www.natalimak1.narod.ru/aspekty6.htm ). Латинские квадраты этой пары содержат подквадраты 5-го порядка. Как вы думаете, можно добавить к этой паре один или два ортогональных латинских квадрата?

[Nataly-Mak]

В статье "О группах MOLS 18-го порядка" показала преобразование недиагонального латинского квадрата 18-го порядка, в котором есть диагональ, состоящая из одинаковых элементов (этот квадрат приведён выше). Это самый сложный случай, потому что никакая трансформация тождественной перестановки чисел не может сразу превратить этот латинский квадрат в нетрадиционный магический квадрат. Вот тут и пригодились перестановки столбцов. Сначала были переставлены всего два столбца; это привело к появлению в рассматриваемой диагонали двух других элементов. А потом уже было применено преобразование трансформации тождественной перестановки чисел. Но при этом необходимо помнить, что все перестановки строк и/или столбцов в латинском квадрате обязательно надо выполнять и в его ортогональном соквадрате, иначе нарушится ортогональность квадратов.
Итак, самый сложный случай тоже рассмотрен, и в этом случае латинский квадрат превращается в нетрадиционный магический квадрат.
maxal
Вы высказали определённое предположение: "можно придумать такой пример, для которого это утверждение неверно". Вы уверены в том, что можно такой пример придумать? Или это только ваше ни на чём неоснованное предположение?
Если бы высказанное утверждение было неверно, то Эйлер наверняка потребовал бы от пары ОЛК диагональности обоих латинских квадратов. Однако он этого не потребовал. Значит, логично предположить, что метод латинских квадратов работает для любой пары ОЛК, а не только для диагональных ортогональных ЛК (или для таких недиагональных ЛК, в которых есть нужные суммы в диагоналях, как например, в методе Делаира для квадратов нечётного порядка).

[maxal]

Nataly-Mak
Моя фраза о примере была предварена "я думаю", означающей лишь предположение (основанное на интуиции). Конечно, если бы у меня было доказательство - я бы его представил.
Из того, что Эйлер решил какие-то частные примеры, не следует, что то же самое можно проделать в общем случае. В любом случае, делать из этого какие-либо далеко идущие выводы я бы не спешил. Может, это и верно в общем случае, а может, и нет. Я склоняюсь ко второму.

Nataly-Mak в сообщении #191240 писал(а):

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

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

[Nataly-Mak]

maxal писал(а):

Из того, что Эйлер решил какие-то частные примеры, не следует, что то же самое можно проделать в общем случае. В любом случае, делать из этого какие-либо далеко идущие выводы я бы не спешил.

Я тоже не спешу
Вчера строила по пункту 3.50 из указанной выше книги группу MOLS 21-го порядка
( http://www.natalimak1.narod.ru/mols20_21.htm ). Опять один квадрат "потеряла". Ведь для построения пяти квадратов нужна матрица из 7 строк, а у меня получается матрица только из 6 строк. Где взять седьмую строку, никак не могу понять.

[tolstopuz]

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

Опять один квадрат "потеряла". Ведь для построения пяти квадратов нужна матрица из 7 строк, а у меня получается матрица только из 6 строк. Где взять седьмую строку, никак не могу понять.

Действительно, я вначале не заметил эту тонкость. Но все оказалось просто - к квадратам, полученным из любой полной (без прочерков) разностной матрицы, можно добавить тривиальный квадрат - первая строка $(1 \ldots n)$, остальные циклически переставлены.

[Nataly-Mak]

Вот спасибо! И что бы я без вас делала!
Я такой квадрат добавила:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14
14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13
13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12
12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11
11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10
10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9
9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8
8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1

А вы?
Теперь очень прошу вас помочь разобраться с методом построения групп MOLS в статье Wojtas. У меня ничего не получается. Может быть, у него другая система заполнения квадратов. Вот, например, при заполнении первого латинского квадрата у меня так получается: в первой строке появляется второй раз число 6. Дальше я не стала заполнять, поставила прочерки, потому что уже ясно, что неправильный квадрат получается.

1 - - - - - 6 13 4 11 2 18 9 6 17 14 5 12 3 10
11 2 - - - - - - 14 5 12 3 19 10 7 18 15 6 13 4
5 12 3 - - - - - - 15 6 13 4 20 11 8 19 16 7 14
15 6 13 4 - - - - - - 16 7 14 5 1 12 9 20 17 8
9 16 7 14 5 - - - - - - 17 8 15 6 2 13 10 1 18
19 10 17 8 15 6 - - - - - - 18 9 16 7 3 14 11 2
3 20 11 18 9 16 7 - - - - - - 19 10 17 8 4 15 12
13 4 1 12 19 10 17 8 - - - - - - 20 11 18 9 5 16
17 14 5 2 13 20 11 18 9 - - - - - - 1 12 19 10 6
7 18 15 6 3 14 1 12 19 10 - - - - - - 2 13 20 11
12 8 19 16 7 4 15 2 13 20 11 - - - - - - 3 14 1
2 13 9 20 17 8 5 16 3 14 1 12 - - - - - - 4 15
16 3 14 10 1 18 9 6 17 4 15 2 13 - - - - - - 5
6 17 4 15 11 2 19 10 7 18 5 16 3 14 - - - - - -
20 7 18 5 16 12 3 20 11 8 19 6 17 4 15 - - - - -
10 1 8 19 6 17 13 4 1 12 9 20 7 18 5 16 - - - -
14 - 2 9 20 7 18 14 5 2 13 10 1 8 19 6 17 - - -
4 - - 3 10 1 8 19 15 6 3 14 11 2 9 20 7 18 - -
8 - - - 4 11 2 9 20 16 7 4 15 12 3 10 1 8 19 -
18 - - - - 5 12 3 10 1 17 8 5 16 13 4 11 2 9 20

Где я ошибаюсь?
Статью Wojtas здесь можно посмотреть:
http://www.natalimak1.narod.ru/mk/wojtas.pdf
В этой статье ещё рассказывается о построении групп MOLS 24-го и 40-го порядков. И в этих построениях пока ничего не поняла. Скорее всего, у Wojtas какой-то другой метод и квадраты заполняются по другой системе.

[tolstopuz]

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

Где я ошибаюсь?

Там используется не группа $\mathbb{Z}_{20}$, а группа $\mathbb{Z}_{10}\oplus\mathbb{Z}_2$. В переводе на простой язык это означает, что все числа представляются в виде $2a+b$, а сложение идет без переноса из младшей части в старшую. Например, $1+1=0$, $3+5=(2\cdot1+1)+(2\cdot2+1)=3\cdot2+0=6$. То есть если в матрице написано четное число, то оно крутится как обычно. А если нечетное, то вот по такому кругу:

$$1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18.$$

[Nataly-Mak]

У меня опять не получилось
Прошу прощения за бестолковость. Ничего пока не поняла с суммой двух абелевых групп. Действовала по рекомендации: от чётного числа двигалась по обычному кругу, а от нечётного числа – по данному вами кругу. Вот что у меня получилось:

0 16 9 4 17 12 5 10 3 8 1 17 8 5 16 13 4 11 2 9
10 1 19 8 7 16 15 4 13 2 11 0 18 9 6 17 14 5 12 3
4 11 2 18 11 6 19 14 7 12 5 10 3 19 10 7 18 15 6 13
14 5 12 3 1 10 9 18 17 6 15 4 13 2 0 11 8 19 16 7
8 15 6 13 4 0 13 8 1 16 9 14 7 12 5 1 12 9 0 17
18 9 16 7 14 5 3 12 11 0 19 8 17 6 15 4 2 13 10 1
2 19 10 17 8 15 6 2 15 10 3 18 11 16 9 14 7 3 14 11
12 3 0 11 18 9 16 7 5 14 13 2 1 10 19 8 17 6 4 15
16 13 4 1 12 19 10 17 8 4 17 12 5 0 13 18 11 16 9 5
6 17 14 5 2 13 0 11 18 9 7 16 15 4 3 12 1 10 19 8
11 7 18 15 6 3 14 1 12 19 10 6 19 14 7 2 15 0 13 18
1 10 8 19 16 7 4 15 2 13 0 11 9 18 17 6 5 14 3 12
15 0 13 9 0 17 8 5 16 3 14 1 12 8 1 16 9 4 17 2
5 14 3 12 10 1 18 9 6 17 4 15 2 13 11 0 19 8 7 16
19 4 17 2 15 11 2 19 10 7 18 5 16 3 14 10 3 18 11 6
9 18 7 16 5 14 12 3 0 11 8 19 6 17 4 15 13 2 1 10
13 8 1 6 19 4 17 13 4 1 12 9 0 7 18 5 16 12 5 0
3 12 11 0 9 18 7 16 14 5 2 13 10 1 8 19 6 17 15 4
7 2 15 10 3 8 1 6 19 15 6 3 14 11 2 9 0 7 18 14
17 6 5 14 13 2 11 0 9 18 16 7 4 15 12 3 10 1 8 19

Очевидно, что квадрат неправильный. Где я на этот раз ошибаюсь?

[tolstopuz]

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

Где я на этот раз ошибаюсь?

По хитрому кругу надо крутить не только сами числа, которые пишутся в матрицу, но и номера строк и столбцов. Например, второй столбец $(0, 1, 10, 11, 3)$ работает так:

$$(0, 1, 10, 11, 3)$$

$$(1, 0, 11, 10, 2)$$

$$(2, 3, 12, 13, 5)$$

$$(3, 2, 13, 12, 4)$$

и т. д.

[Nataly-Mak]

Ёлки зелёные! Ну и "закручено"!
Но позвольте опять не понять
Из того, что вы написали, я так поняла, что для второго, третьего и т. д. квадратов надо номера строк и столбцов "крутить"? А для первого латинского квадрата надо брать номера строк и столбцов так, как есть, ничего "не крутить"? Так? Но у меня не получается уже первый латинский квадрат.
Да-а-а, похоже эта карусель не для меня. С детства плохо переношу карусель

[tolstopuz]

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

Но у меня не получается уже первый латинский квадрат.

Это вам к празднику

 0 11  9 18 17  6  5 14  3 12  1 10  8 19 16  7  4 15  2 13
10  1 19  8  7 16 15  4 13  2 11  0 18  9  6 17 14  5 12  3
 4 15  2 13 11  0 19  8  7 16  5 14  3 12 10  1 18  9  6 17
14  5 12  3  1 10  9 18 17  6 15  4 13  2  0 11  8 19 16  7
 8 19  6 17  4 15 13  2  1 10  9 18  7 16  5 14 12  3  0 11
18  9 16  7 14  5  3 12 11  0 19  8 17  6 15  4  2 13 10  1
 2 13 10  1  8 19  6 17 15  4  3 12 11  0  9 18  7 16 14  5
12  3  0 11 18  9 16  7  5 14 13  2  1 10 19  8 17  6  4 15
16  7  4 15 12  3 10  1  8 19 17  6  5 14 13  2 11  0  9 18
 6 17 14  5  2 13  0 11 18  9  7 16 15  4  3 12  1 10 19  8
11  0 18  9  6 17 14  5 12  3 10  1 19  8  7 16 15  4 13  2
 1 10  8 19 16  7  4 15  2 13  0 11  9 18 17  6  5 14  3 12
15  4 13  2  0 11  8 19 16  7 14  5 12  3  1 10  9 18 17  6
 5 14  3 12 10  1 18  9  6 17  4 15  2 13 11  0 19  8  7 16
19  8 17  6 15  4  2 13 10  1 18  9 16  7 14  5  3 12 11  0
 9 18  7 16  5 14 12  3  0 11  8 19  6 17  4 15 13  2  1 10
13  2  1 10 19  8 17  6  4 15 12  3  0 11 18  9 16  7  5 14
 3 12 11  0  9 18  7 16 14  5  2 13 10  1  8 19  6 17 15  4
 7 16 15  4  3 12  1 10 19  8  6 17 14  5  2 13  0 11 18  9
17  6  5 14 13  2 11  0  9 18 16  7  4 15 12  3 10  1  8 19

[Nataly-Mak]

Спасибо, конечно
Но без объяснений - плохой подарок.
Первоначально числа в матрицу вписаны так же, как это сделала я. Правильно? А что вы дальше делаете, как "пляшете" от этих начальных чисел, совершенно непонятно. Хотя я сегодня ещё не выпивала, но отупела уже совсем

[tolstopuz]

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

А что вы дальше делаете, как "пляшете" от этих начальных чисел, совершенно непонятно.

В исходной матрице написано $(0, 0, 0)$ - рисуем из левого верхнего угла диагональ $0, 1, 2, 3, \ldots$
$(0, 1, 10)$ - обвиваем ее зигзагом числами $10, 11, 12, 13, \ldots$
...
$(0, 10, 11)$ - из середины стороны рисуем диагональ $11, 10, 13, 12, \ldots$
$(0, 11, 1)$ - обвиваем ее зигзагом числами $1, 0, 3, 2, \ldots$

Кстати, результат выглядит так, как будто четыре одинаковых квадрата $5\times5$ приставили друг к другу, а потом каждую клетку раздули в квадратик $2\times2$.

Привыкайте, дальше будет еще хитрее