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

[Nataly-Mak]

maxal писал(а):

Это мы уже обсуждали.

Можно прямую ссылку на обсуждение именно вопроса существования ортогонального классического ЛК для любого классического ЛК? Слаба памятью стала
Как я помню, обсуждался вопрос построения ОЛК к данному. В этом обсуждении говорилось, что строить такой ОЛК пока никто не умеет. То есть кроме простого перебора здесь не придумали никаких эффективных алгоритмов.
На чём конкретно основан ваш отрицательный ответ? Пожалуйста, повторите, если вы уже об этом обосновании говорили. Разумеется, не считаем классический ЛК 6-го порядка, для которого доказано, что не существует никакого ОЛК. Я говорю о порядках больших 6.

maxal писал(а):

А определение того, существует или нет, если мне не изменяет память, ничуть не проще чем нахождение оргонального квадрата к данному.

Это как? То есть, как я понимаю, ответить на вопрос "существует или нет" можно только найдя этот самый ОЛК? А если никто пока не знает, как его найти. Неужели нет никаких критериев, по которым можно определить для конкретного классического ЛК, есть ли для него ортогональный?

Добавлено спустя 1 час 42 минуты 29 секунд:

Да, древние знали толк в квадратах!
Алгоритм Агриппы, по которому составлен представленный здесь ЛК 12-го порядка, восхищает своей гармонией. По этому алгоритму составляю ЛК 8-го порядка:

0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
1 0 7 6 5 4 3 2
2 3 4 5 6 7 0 1
6 7 0 1 2 3 4 5
5 4 3 2 1 0 7 6
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3

Спрашивается: есть ли для этого ЛК ортогональный? Смотрю на группу ОЛК 8-го порядка, построенную Maple. И вижу, что все ЛК этой группы (7 штук) получаются друг из друга перестановкой строк. Делаю аналогичную перестановку строк в ЛК, построенном по алгоритму Агриппы. И ОЛК получен! Вот он:

0 1 2 3 4 5 6 7
1 0 7 6 5 4 3 2
6 7 0 1 2 3 4 5
3 2 1 0 7 6 5 4
5 4 3 2 1 0 7 6
4 5 6 7 0 1 2 3
7 6 5 4 3 2 1 0
2 3 4 5 6 7 0 1

Правда, эта пара ОЛК пригодна только для построения полумагического квадрата (по алгоритму Агриппы для порядка 8 строится магический квадрат, но у Агриппы второй ЛК обобщённый). Вполне возможно, что этот полумагический квадрат тоже можно исправить перестановкой строк, как это было сделано с полумагическим квадратом 10-го порядка. Надо попробовать.
Итак, если проделать все аналогичные перестановки строк в ЛК Агриппы 8-го порядка, то, кажется, получается новая группа попарно ортогональных классических латинских квадратов 8-го порядка, которую я так давно хотела увидеть.
К сожалению, для квадрата 12-го порядка у меня нет такой группы ОЛК, и аналогию взять негде. Но можно предположить, что из ЛК 12-го порядка тоже можно получить ОЛК простой перестановкой строк. Это гипотеза. Надо её проверять.

[maxal]

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

Можно прямую ссылку на обсуждение именно вопроса существования ортогонального классического ЛК для любого классического ЛК?

Вот: http://dxdy.ru/post145064.html#145064

[Nataly-Mak]

Ну, немудрено, что я этого не помню! Вопрос-то был задан не мной. А ответ не на мой вопрос я могла прочитать очень бегло и сразу забыть.

[Aleks-Sid]

Nataly-Mak

Я читал где-то, что комбинаторным способом были получены ортогональные ЛК порядков 10, 14, 18 и 22. Но нигде их воочию не видел. Хотелось бы взглянуть, чтобы понять суть их построений. У меня получаются комбинированные ЛК, то есть первый классический, а второй обобщенный.

[Nataly-Mak]

Aleks-Sid писал(а):

Я читал где-то, что комбинаторным способом были получены ортогональные ЛК порядков 10, 14, 18 и 22. Но нигде их воочию не видел.

Это вы читали, возможно, в книге М. Гарднера. Всё, что могла, показала здесь:
http://www.natalimak1.narod.ru/aspekty.htm

[Aleks-Sid]

Nataly-Mak
Я никак не могу уловить закономерности построения чисел в ЛК 10х10. Без этого ни на дюйм не продинуться в общем понимании задачи.

[Nataly-Mak]

Наконец-то вы оценили сложность задачи.
В 1958 году Паркер построил первую пару ОЛК 10-го порядка. Однако она не пригодна для построения магического квадрата (по крайней мере та, которая приведена в книге М. Гарднера, Паркер, может быть, не одну пару составил, а несколько, и среди них, возможно были пригодные для построения МК). Мне удалось получить из пары ОЛК Паркера пару ОЛК, пригодную для построения МК.
А пары диагональных ОЛК 10-го порядка были найдены лишь лет 35 спустя.
Построить пары диагональных ОЛК ещё сложнее, чем просто пары ОЛК, как я поняла.
Если же ортогональные латинские квадраты не диагональные, то их ещё надо преобразовывать, чтобы из них можно было построить МК (что я сделала, например, с парой не диагональных ОЛК 22-го порядка).
А впрочем, задача составления пар ОЛК давно решена для всех порядков (кроме 2 и 6). Есть куча статей (например, в моей статье приведён солидный список литературы). Так что, можно не изобретать велосипед, а просто разобраться в статьях, которые все, как нарочно, по-английски написаны. Я очень надеялась на машинный перевод, который мне организовали. Прислали перевод трёх статей. Но этот перевод понятен меньше, чем оригинал.
Если говорить о порядках $n = 4k + 2$, я придумала красивую схему составления первого латинского квадрата, но составить второй латинский квадрат ортогональный первому не могу. То есть не пыталась даже это сделать, потому что составлять программу для тупого перебора не хочется, а другого способа не вижу.
Можно поискать в Сети статьи по этой теме на русском языке. Этим я ещё не занималась

[Aleks-Sid]

Да... По поводу проблемы есть публикации, но не конкретные. Например, http://mathinfinity.net.ru/blog/latin_square

[Nataly-Mak]

Да, очень богата информацией статья по приведённой вами ссылке
Как мне кажется, ничего путного об ОЛК на русском языке ещё не написали, мне, во всяком случае, не попадалось, хотя я тоже сегодня немного побродила по Интернету. Мне повезло: я нашла очень интересный греко-латинский квадратик 10-го порядка. Вот по этой ссылке:
http://www.mi.ras.ru/spm/pdf/011.pdf
В этой статье, которая посвящена Л. Эйлеру, написано, что именно Эйлер первым предложил использовать греко-латинские квадраты для построения МК. Значит, Эйлер является автором метода латинских квадратов. Таким образом, метод латинских квадратов имеет своё начало в XVIII веке. Интересен такой факт: Эйлер не требовал от ортогональных ЛК диагональности, и поэтому составляемые греко-латинские квадраты давали не магические, а полумагические квадраты (в диагоналях суммы чисел не были равны магической константе квадрата). Этот факт даёт основание предположить (я уже делала такое предположение на основании квадратов Франклина), что в XVIII веке полумагические и магические квадраты не различались.
Вчера один очень хороший человек перевёл мне маленький фрагмент из статьи на английском языке. В этом фрагменте содержится очень важное сообщение о том, что если существуют диагональные ОЛК порядков $n_1$ и $n _2$, то можно составить ОЛК порядка $n_1$x$n_2$. Это получается некоторый аналог метода составных квадратов для МК. Вот только я пока не знаю, как именно это можно сделать. Например, у нас есть пары диагональных ОЛК порядка 4 и порядка 5. Как составить пару диагональных ОЛК порядка 20?
Одним словом, надо изучать статьи на английском.

[Nataly-Mak]

Сейчас отправила эту статью на перевод:
“Three Mutually Orthogonal Latin Squares of Order 14” (D. T. Todorov)
Жду с трепетом этот перевод, потому что вряд ли снова смогу в нём что-нибудь понять. А так хочется понять, как же всё-таки строятся ОЛК 14-го порядка.
В статье есть три фрагмента. Вот два из них:

a 0 1 3 2 4 5 6 7 8 9 10 11 12
0 a 2 12 10 7 9 5 4 1 11 8 3 6
1 2 a 9 5 3 12 7 11 0 4 6 8 10
3 12 9 a 6 2 7 11 1 5 10 0 4 8

a 0 1 3 2 4 5 6 7 8 9 10 11 12
0 a 7 4 5 8 10 1 3 2 6 12 9 11
1 7 a 12 4 10 3 5 8 11 0 2 6 9
3 4 12 a 9 1 6 11 2 10 8 0 7 5

Третий похож на эти два. Что означают эти фрагменты и с чем их надо кушать? Значение символа $a$, который в статье почему-то похож на символ бесконечности, я предполагаю равным 13. Это вроде какие-то массивы, с помощью которых можно строить ОЛК.
Понятно, что любой из этих фрагментов может быть началом латинского квадрата 14-го порядка. Понятно и то, что латинские квадраты, начинающиеся с этих фрагментов, не могут быть ортогональными. Я взяла первый из этих фрагментов и простым подбором составила из него такой латинский квадрат:

13 0 1 3 2 4 5 6 7 8 9 10 11 12
0 13 2 12 10 7 9 5 4 1 11 8 3 6
1 2 13 9 5 3 12 7 11 0 4 6 8 10
3 12 9 13 6 2 7 11 1 5 10 0 4 8
2 10 5 6 13 8 1 3 0 4 7 9 12 11
4 7 3 2 8 13 6 9 12 10 0 11 1 5
5 9 12 7 1 6 13 0 8 11 3 4 10 2
6 5 7 11 3 9 0 13 10 12 8 1 2 4
7 4 11 1 0 12 8 10 13 6 5 2 9 3
8 1 0 5 4 10 11 12 6 13 2 3 7 9
9 11 4 10 7 0 3 8 5 2 13 12 6 1
10 8 6 0 9 11 4 1 2 3 12 13 5 7
11 3 8 4 12 1 10 2 9 7 6 5 13 0
12 6 10 8 11 5 2 4 3 9 1 7 0 13

А ортогональный этому квадрат составить не могу.
По придуманной мной схеме составила ещё один ЛК 14-го порядка. Вот он:

0 2 4 6 8 10 12 13 3 5 7 9 11 1
12 1 3 5 7 9 11 0 13 4 6 8 10 2
11 0 2 4 6 8 10 12 1 13 5 7 9 3
10 12 1 3 5 7 9 11 0 2 13 6 8 4
9 11 0 2 4 6 8 10 12 1 3 13 7 5
8 10 12 1 3 5 7 9 11 0 2 4 13 6
13 9 11 0 2 4 6 8 10 12 1 3 5 7
6 13 10 12 1 3 5 7 9 11 0 2 4 8
5 7 13 11 0 2 4 6 8 10 12 1 3 9
4 6 8 13 12 1 3 5 7 9 11 0 2 10
3 5 7 9 13 0 2 4 6 8 10 12 1 11
2 4 6 8 10 13 1 3 5 7 9 11 0 12
1 3 5 7 9 11 13 2 4 6 8 10 12 0
7 8 9 10 11 12 0 1 2 3 4 5 6 13

Но тоже не могу составить ортогональный ему квадрат.
Помещаю указанную статью сюда:
http://www.natalimak1.narod.ru/mk/mols14.pdf
Может быть, кто-нибудь поможет разобраться в секрете построения пары ОЛК 14-го порядка.

[Nataly-Mak]

Aleks-Sid писал(а):

Я никак не могу уловить закономерности построения чисел в ЛК 10х10.

Кажется, я поняла закономерности построения пары ОЛК порядка 10. Смотрите в статье
“Новые аспекты метода латинских квадратов (часть IV)”. В статье, где я взяла эти схемы, написано, что по такому же алгоритму строятся пары ОЛК любого порядка $n = 10(mod 12)$. Если овладеть этим алгоритмом, то для третьей части порядков рассматриваемой серии $n = 4k + 2$ задача будет решена. В своей статье я нарисовала заготовки для пары ОЛК 22-го порядка, но пока не достроила квадраты до конца. Надо это додумать, немножко осталось

[Aleks-Sid]

Nataly-Mak

Да, какая-то закономерность просматривается. Но было бы более логично делить 10 не на 3 и 7 частей, а на 5 и 5. То есть иметь дело с квадрантами. Может, получится?

[Nataly-Mak]

С квадратами 22-го порядка у меня всё уже получилось (см. в той же статье). Схема составления стала совсем понятна. Одно плохо в построенной паре ОЛК: латинские квадраты не диагональные. Поэтому пара ОЛК пригодна только для построения полумагических квадратов. Чтобы из неё можно было построить магические квадраты, ЛК надо сначала преобразовать.
Так что остаётся нерешённой задача составления пар диагональных ОЛК для данных порядков - $n = 10(mod 12)$, кроме порядка 10, для которого такие пары у меня уже есть.
Для остальных порядков рассматриваемой серии $n = 4k + 2$ вообще пока нет ничего.
Вчера получила машинный перевод статьи об ОЛК 14-го порядка. Как я и предполагала - абсолютный мрак.
Здесь куда все подевались-то? Или всё ещё празднуют Новый год и Рождество? Как я поняла, тут знатоков английского - пруд пруди. Кстати, Aleks-Sid, вы вроде писали, что знаете английский. Может быть, посмотрите, что там в статье об ОЛК 14-го порядка написано? (статья лежит на моём сайте, ссылка выше).

[Aleks-Sid]

Nataly-Mak

Статью я скачал, просмотрел бегло, но что-то тоже не понял. У меня накопилась усталость и не могу мобилизоваться на новый штурм. Что касается полумагических ЛК, то я их нашел пачками и схемы их построения более закономерные. Но что толку? Ведь нужны и магические суммы в диагоналях. А тут моя комбинаторная прога ничего не нашла

[Nataly-Mak]

Aleks-Sid писал(а):

Что касается полумагических ЛК, то я их нашел пачками и схемы их построения более закономерные. Но что толку? Ведь нужны и магические суммы в диагоналях. А тут моя комбинаторная прога ничего не нашла

Какие ЛК вы нашли пачками? Вы составили пары ортогональных классических латинских квадратов, в которых нет сумм в диагоналях? Так это ерунда! Я такие квадраты элементрарно преобразовываю и они у меня получаются магические. В моей статье есть несколько таких примеров.
У вас есть пара классических ОЛК 14-го порядка? А 18-го? Неважно, если эти ЛК не диагональные (то есть не магические).