Латинские квадраты

[Nataly-Mak]

При рассмотрении метода построения идеальных магических квадратов с помощью орогональных латинских квадратов мне встретилась задача составления ортогонального латинского квадрата к одному обобщённому латинскому квадрату. Вот этот квадрат:

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

При этом составленный ортогональный латинский квадрат должен быть (если смотреть на него как на нетрадиционный магический квадрат) идеальным магическим квадратом с магической константой 36 (таковым является и исходный латинский квадрат).
Мне удалось составить один латинский квадрат ортогональный данному, но он получился только ассоциативным, но не пандиагональным.
Хочется узнать, можно ли составить ортогональный латинский квадрат с нужными условиями.
Кто знает ссылки, где рассматриваются методы составления ортогональных латинских квадратов к обобщённым (а также к нормальным) латинским квадратам, напишите, пожалуйста. Я составила очень много ортогональных латинских квадратов, но как их составлять, так и не знаю
Подробности см. в статье ‹…›
Написала программу для составления нужного латинского квадрата, но она получилась "долгоиграющая", то есть очень долго выполняется; не смогла дождаться, когда она выполнится до конца.
Определения для латинских квадратов есть в Википедии в статье "Латинский квадрат", а для магических квадратов соответственно в статье "Магический квадрат".

ссылка удалена // нг

[Sonic86]

Я в Википедию не лазил (далее следуют сиротские ссылки на плохой диал-ап канал).
По лекциям у меня следующее.
Df1. Пусть $a_{i,j} \in {0,1,...,n-1}, i,j \in {0,1,...,n-1}$. Тогда $A=(a_{i,j})$ - ЛК (латин. квадрат) $\longleftrightarrow$
в каждой строке и каждом столбце элементы $a_{i,j}$ различны.
Df2. Наложением A&B квадратов $A=(a_{i,j}), B=(b_{i,j})$ размерности n называется квадрат
$A&B = ( (a_{i,j}, b_{i,j}) )$. (поэлементное декартово произведение).
Df3. А и В - ортогональны $\longleftrightarrow$ A&B состоит из различных элементов.


У меня есть Рыбников. Там про ЛК есть, но видимо, сложно. Могу скинуть. А так - подумать надо.

[maxal]

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

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

Я уже как-то давал вам ссылку, повторю еще раз:
Холл М. — Комбинаторика
глава 13 там недвусмысленно там называется "Ортогональные латинские квадраты".

[Nataly-Mak]

Спасибо за определения. Точно такие же определения я нашла в книге Ю. В. Чебракова.
Maxal, я смотрела по указанной вами ссылке. Но, к сожалению, прочитать интересующий меня раздел не смогла. Там написано, что скачать книгу нельзя (недвусмысленно). Тогда я поискала, как её хоть на экране монитора посмотреть, и не нашла. Вышел только Предметный указатель, в котором, да, видела: Ортогональные латинские квадраты - 244. Может быть, я что-то не увидела? Подскажите, пожалуйста, как же в эту книгу заглянуть?
Ну, а как насчёт моего конкретного квадратика? Есть решение?

[maxal]

Nataly-Mak, забирайте отсюда:
http://eqworld.ipmnet.ru/ru/library/boo ... 970ru.djvu

[Nataly-Mak]

О, спасибо, Maxal! Скопировала, но ещё не посмотрела. Думаю, что очень интересный для меня материал.
А задача моя снимается. Я её только что решила. Ортогональный квадрат получен так: сначала исходный квадрат повёрнут на 90 градусов против часовой стрелки, а затем отражён относительно горизонтальной оси симметрии. Можно и так: поворот на 90 градусов по часовой стрелке с последующим отражением относительно вертикальной оси симметрии. А можно ещё проще: отражение относительно главной диагонали.
Просто вспомнила, что в самых последних моих статьях (которые написаны буквально на днях) встречается такой метод составления ортогональных латинских квадратов.
Из моей пары ортогональных латинских квадратов получился такой квадрат:

22  04  43  57  30  72  83  68  17
40  55  37  78  81  63  14  26  02
34  73  88  60  12  24  08  47  50
75  87  06  11  23  35  46  52  61
03  18  21  32  44  56  67  70  85
27  36  42  53  65  77  82  01  13
38  41  80  64  76  28  00  15  54
86  62  74  25  07  10  51  33  48
71  20  05  16  58  31  45  84  66

Кажется, этот квадрат называется греко-латинским?
Симметрия в этом квадрате изумительная. Из этого квадрата и получается идеальный магический квадрат 9-ого порядка, надо только заменить числа в девятеричной системе счисления на их десятичные эквиваленты. В этом и состоит метод построения идеальных магических квадратов с помощью двух ортогональных латинских квадратов, исследованию которого я посвятила уже несколько статей. Жаль, что здесь нельзя давать ссылки

[Nataly-Mak]

Начала писать обзорную статью о методах построения магических квадратов. Штудирую материалы по этой теме во всех источниках. Вот в книге Чебракова нахожу "Метод латинских квадратов" (Ю. В. Чебраков. Магические квадраты. Терия чисел, алгебра, комбинаторный анализ. - С.-Петербург, 1995; стр.96-97).
Цитата из книги: "Первый латинский квадрат строят следующим образом: а) произвольно заполняют нижний горизонтальный ряд квадратной таблицы n*n целыми числами от 0 до n-1, следя лишь за тем, чтобы последняя клетка горизонтального ряда была заполнена числом k=[n/2]"; б) остальные горизонтальные ряды таблицы заполняют снизу вверх так, чтобы каждый следующий ряд получался из предыдущего циклической перестановкой - первое число переносится в конец строки. Второй латинский квадрат получается из первого путём его поворота на девяносто градусов".
Ну, как строится первый латинский квадрат, понятно. В книге дана иллюстрация построения. Вот первый латинский квадрат, изображённый на иллюстрации:

2  1  4  0  3
3  2  1  4  0
0  3  2  1  4
4  0  3  2  1
1  4  0  3  2

А как составляется второй латинский квадрат, убей не понимаю! Целый час поворачивала первый латинский квадрат, но так и не смогла получить тот квадрат, который изображён на картинке у автора книги. Вот какой второй латинский квадрат дан автором:

0  3  4  1  2
3  4  1  2  0
4  1  2  0  3
1  2  0  3  4
2  0  3  4  1

Пожалуйста, объясните мне, какой здесь поворот на 90 градусов? Вокруг чего? В какую сторону?
Вот какой магический квадрат построил автор из пары составленных им ортогональных латинских квадратов:

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

Тогда я составила второй латинский квадрат по-своему: отражение первого латинского квадрата относительно горизонтальной оси симметрии. И вот какой магический (к тому же и ассоциативный; ну, ассоциативность обеспечивается удачно составленным первым латинским квадратом - он является нетрадиционным ассоциативным магическим квадратом; мой второй латинский квадрат тоже является нетрадиционным ассоциативным магическим квадратом, в отличие от второго квадрата Чебракова) квадрат получен из моей пары ортогональных латинских квадратов:

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

Если мы будем строить магический квадрат седьмого порядка по Чебракову, то как составить второй латинский квадрат? Первый латинский квадрат может быть, например, такой:

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

Правильно Теперь скажите, куда и как надо повернуть на 90 градусов этот латинский квадрат, чтобы получить второй латинский квадрат по Чебракову
Продолжаю проверять свой способ. Составляю второй латинский квадрат отражением первого относительно горизонтальной оси симметрии. Cтрою из полученной пары ортогональных латинских квадратов магический квадрат:

24  20  36  2  12  35  46
48  22  16  40  7  11  31
29  44  26  21  39  3  13
9  33  49  25  17  41  1
5  14  32  45  27  15  37
42  4  10  34  43  23  19
18  38  6  8  30  47  28

Магический квадрат получился.

[maxal]

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

В книге дана иллюстрация построения. Вот первый латинский квадрат, изображённый на иллюстрации:

2  1  4  0  3
3  2  1  4  0
0  3  2  1  4
4  0  3  2  1
1  4  0  3  2

А как составляется второй латинский квадрат, убей не понимаю! Целый час поворачивала первый латинский квадрат, но так и не смогла получить тот квадрат, который изображён на картинке у автора книги. Вот какой второй латинский квадрат дан автором:

0  3  4  1  2
3  4  1  2  0
4  1  2  0  3
1  2  0  3  4
2  0  3  4  1

Пожалуйста, объясните мне, какой здесь поворот на 90 градусов? Вокруг чего? В какую сторону?

А вы точно второй квадрат отобразили? Результатом поворота на 90 градусов первого квадрата (вокруг своего центра) против часовой стрелки является:

3  0  4  1  2
0  4  1  2  3
4  1  2  3  0
1  2  3  0  4
2  3  0  4  1

[Nataly-Mak]

Ну, поворот квадрата на 90 градусов против часовой стрелки вокруг центра - это все, наверное, знают. Второй латинский квадрат Чебракова я отобразила (скопировала из книжки) правильно. Это можно проверить по готовому магическому квадрату, который автор построил далее так (цитата):
"2. Преобразовывают полученные два латинских квадрата путём умножения каждого числа одного квадрата на n и увеличения на 1 каждого числа другого квадрата. 3. Производят поклеточно суммирование двух преобразованных на втором этапе квадратов".
Я построенный магический квадрат проверила, он построен описанным способом именно из той пары ортогональных латинских квадратов, которые приводит автор на картинке и которые мной скопированы. Готовый магический квадрат тоже здесь показан.

[Nataly-Mak]

Вот ещё одна интересная пара ортогональных латинских квадратов. Я получила её при рассмотрении метода альфила (так в древние времена назывался шахматный слон).
Первый латинский квадрат:

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

Второй латинский квадрат:

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

Как здесь второй латинский квадрат получается из первого? Никакие доселе известные мне способы превращения первого латинского квадрата во второй не действуют.

[Nataly-Mak]

Если кто-то вдруг ломает голову над "поворотом квадрата по Чебракову", можете прекратить это занятие. Чебраков допустил явный ляпсус. Я нашла разгадку этой задачи в книге М.М. Постникова, Магические квадраты, М:. Наука, 1964.Книги этой у меня нет, но один товарищ (читатель моих статей о МК) любезно прислал мне фотокопии заинтересовавшей меня главы, в которой описывается квазилинейный метод Делаира. Постников не называет квадраты, участвующие в построении магических квадратов, латинскими, он называет их вспомогательными, но сути дела это не меняет. Посмотрев приведённый Постниковым пример построения магического квадрата 5-ого порядка с помощью двух вспомогательных (=латинских) квадратов, я всё поняла. Подробности изложу в статье.

[Sonic86]

Можно вопрос? Для данного латинского квадрата сколько существует ортогональных?

[Nataly-Mak]

Вы имеете в виду латинский квадрат 5-ого порядка Чебракова? Думаю, что как минимум 24 ортогональных латинских квадрата для него существуют. Два я уже показала здесь, один Чебраковский, другой мой. Дело в том, что по методу Делаира второй вспомогательный (=латинский) квадрат не получается из первого никакими поворотами. Он строится самостоятельно по правилу, аналогичному построению первого латинского квадрата, только произвольная перестановка чисел вписывается не в нижнюю, а в верхнюю строку. Я уже изложила метод Делаира в статье "Методы построения магических квадратов".

[Nataly-Mak]

Рассматривая в статье “Методы построения магических квадратов” метод окаймлённых квадратов, заинтересовалась концентрическими магическими квадратами. Построение таких квадратов привело меня к такому латинскому квадрату, который составлен только наполовину. Требуется достроить этот обобщённый латинский квадрат и, если решение есть, построить к нему ортогональный латинский квадрат. Латинский квадрат такой:

5  6  7  8  0  1  2  3  4
6  a  b  c  d  e  f  g  2
7  x  1  6  8  4  1  x’ 1
8  y  2  3  5  4  6  y’ 0
0  z  8  5  4  3  0  z’ 8
1  w  2  4  3  5  6  w’ 7
2  t  7  2  0  4  7  t’ 6
3  g’ b’ c’ d’ e’ f’ a’ 5
4  2  1  0  8  7  6  5  3

Переменные с апострофом комплементарны соответствующим переменным без апострофа, например: a+a’=8.
Не уверена, что решение существует, но очень хочется, чтобы существовало

[ha]

Просто латинский квадрат построить легко: a=4,b=7,c=7,d=2,e=0,f=5,g=3,x=0,y=1,z=6,w=8,t=3.