Н. Макарова

 

 ОРТОГОНАЛЬНЫЕ ДИАГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ

 

 

Как я уже не раз писала, пары ортогональных диагональных латинских квадратов – это самый лучший вариант для метода латинских квадратов. В англоязычных статьях ортогональные диагональные латинские квадраты называются Orthogonal Diagonal Latin Squares, и используется аббревиатура ODLS.  Я тоже буду использовать аббревиатуру – ОДЛК.

 

Доказано, что существуют пары ОДЛК всех порядков кроме 2, 3 и 6. Построение пар ОДЛК порядков, являющихся простым числом или степенью простого числа, а также нечётным числом не кратным 3, не вызывает никаких затруднений. Для порядков, представимых в виде произведения двух чисел, и каждое из этих чисел есть порядок, для которого существуют пары ОДЛК, тоже очень легко построить пару ОДЛК методом составных квадратов (см. статью http://www.natalimak1.narod.ru/aspekty7.htm ).

 

Для начала покажу пары ОДЛК 4-го, 8-го и 10-го порядков (рис. 1 – 3). Пары ОДЛК 4-го и 8-го порядка составлены из диагональных латинских квадратов, входящих в стандартные группы MOLS. Пара ОДЛК 10-го порядка взята из статьи “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие, 1992 г.).

 

 

Рис. 1

 

 

Рис. 2

 

 

Рис. 3

 

Пару ОДЛК 12-го порядка я не встречала. А теперь покажу построение пары ОДЛК 14-го порядка. Это построение я нашла в статье “ORTOGONAL DIAGONAL LATIN SQUARES OF ORDER FOURTEEN” (L. Zhu, 1982 г.) Очень оригинальный метод построения, который я затем успешно применила для построения пар ОДЛК 15-го и 18-го порядков.

Заметьте, что эта статья была написана до того, как были построены пары ОДЛК 10-го порядка. В то время проблемными оставались порядки 10, 14, 15, 18 и 26. В этой статье как раз и решается задача для одного из проблемных порядков – 14-го. В 1989 г. была решена задача ещё для трёх проблемных порядков – 15, 18 и 26. Я нашла ссылку вот на такую статью: А. В. Назарок. Пары ортогональных дважды диагональных латинских квадратов порядков 15, 18 и 26. // Комбинаторный анализ. Вып. 32. М.: МГУ, 1989 г. К сожалению, статью мне найти не удалось. И, наконец, в 1992 г. Браун и компания закрывают последний проблемный порядок – 10.

(Обратите внимание: в названии статьи использован термин “дважды диагональных латинских квадратов”. Этим подчёркивается, что в диагональных латинских квадратах в каждой из двух главных диагоналей все элементы различны. В англоязычной литературе встречается аналогичный термин “doubly diagonal latin squares”).

 

Поскольку пары ОДЛК 15-го и 18-го порядков я построила сама по аналогии с парой ОДЛК 14-го порядка, у меня остаётся один проблемный порядок – 26. Кроме этого проблемного порядка, я не знаю, как строить пары ОДЛК и для многих других порядков, например, 12, 21, 24 и т. д. Насколько я поняла, математики эту задачу давно решили, но где найти её решение? Буду очень признательна читателям, если они напишут мне об этом. Очень хотелось бы найти указанную выше статью о парах ОДЛК 15-го, 18-го и 26-го порядков. Интересно, какие пары ОДЛК 15-го и 18-го порядка построены в этой статье (хочется сравнить с построенными мной парами). Кроме того, в этой статье есть построение пары ОДЛК 26-го порядка, которую мне пока построить не удалось.

 

Начну изложение замечательного метода из указанной статьи L. Zhu. Предел моих мечтаний – пара ОДЛК 14-го порядка! А какой оригинальный метод построения этой пары ОДЛК! Сначала строится пара не диагональных ОЛК. Латинские квадраты этой пары содержат латинский подквадрат 4х4 и имеют соответствующую квази-разностную матрицу (КРМ). На рис. 4 – 5 вы видите эту пару ОЛК.

 

Первый латинский квадрат

 

 

Рис. 4

 

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

 

 

Рис. 5

 

В латинских квадратах выделен оранжевым цветом подквадрат 4х4. Понятно, что пара ортогональных латинских подквадратов 4х4, содержащаяся в данных латинских квадратах, может быть заменена на любую другую пару ортогональных латинских квадратов 4-го порядка, состоящих из тех же самых элементов. Такая замена даёт существенно новые (неизоморфные) пары ОЛК 14-го порядка. Символьные элементы a, b, c, d принимают значения 10, 11, 12, 13 в любой комбинации. Обратите внимание на то, что в представленном варианте использована пара диагональных подквадратов 4х4. Это важно для дальнейшего превращения данной пары не диагональных ОЛК в пару ОДЛК.

А теперь посмотрим на КРМ этой пары ОЛК (рис. 6).

 

 

 

Рис. 6

 

Выделенная секция КРМ может варьироваться! Варьирование выполняется следующим образом: берутся все возможные перестановки групп чисел 1, 2, 6, 8 и 5, 6, 7, 8. Конечно, при этом проверяется совместимость третьей и четвёртой строк КРМ по известному критерию. Я составила программу для нахождения всех возможных перестановок, удовлетворяющих критерию совместимости строк, программа выдала 1152 решения. Это значит, что мы имеем 1152 неизоморфные пары ОЛК 14-го порядка такой же структуры. Приведённый вариант выдан программой под № 213. Интересен вариант № 12, покажу этот вариант. КРМ этого решения имеет следующий вид (рис. 7):

 

 

Рис. 7

 

В этом варианте перестановка в группе чисел 1, 2, 6, 8 выбрана одинаковая. На рис. 8 – 9 показана пара ОЛК, построенная по данной КРМ.

 

Первый латинский квадрат (решение № 12)

 

 

Рис. 8

 

Второй латинский квадрат (решение № 12)

 

 

Рис. 9

 

А теперь самый интересный момент – превращение построенной пары ОЛК в пару ОДЛК. Сначала покажу это превращение для первой пары, то есть для пары, приведённой в статье (решение № 213). На рис. 10 – 11 вы видите пару ОДЛК. Латинские квадраты этой пары получаются из латинских квадратов пары ОЛК с рис. 4 – 5 совершенно определённым образом. Я не буду подробно описывать, как именно фрагменты латинских квадратов из пары ОЛК размещаются в новых квадратах, вы всё поймёте по раскраске квадратов. Ещё в паре ОДЛК символьные элементы заменены числовыми значениями.

 

Первый  диагональный латинский квадрат

 

 

Рис. 10

 

Второй диагональный латинский квадрат

 

 

Рис. 11

 

Пара ОДЛК получена. Сразу покажу два магических квадрата, построенные из этой пары ОДЛК методом латинских квадратов. Как уже знают читатели, эта пара ортогональных латинских квадратов сразу пригодна для построения магических квадратов, потому что квадраты этой пары диагональные. На рис. 12 – 13 вы видите магические квадраты 14-го порядка, построенные из данной пары ОДЛК.

 

 

Рис. 12

 

 

Рис. 13

 

В этих магических квадратах первая главная диагональ в точности совпадает, а вторая главная диагональ “перевёрнута”, то есть получена отражением относительно первой главной диагонали.

Мной уже были построены магические квадраты 14-го порядка из пар недиагональных ОЛК. И вот теперь получены самые лучшие магические квадраты данного порядка – из пары ОДЛК.

 

Разумеется, все 1152 варианта пар ОЛК превращаются точно таким же образом в пары ОДЛК. Покажу это на примере пары ОЛК с рис. 8 – 9. На рис. 14 – 15 вы видите новую пару ОДЛК, полученную из этой пары ОЛК.

 

Первый  диагональный латинский квадрат (решение № 12)

 

 

Рис. 14

 

Второй  диагональный латинский квадрат (решение № 12)

 

 

Рис. 15

 

И вот новые магические квадраты, построенные из новой пары ОДЛК (рис. 16 – 17).

 

 

Рис. 16

 

 

Рис. 17

 

Эти магические квадраты имеют точно такие же главные диагонали, как и два магических квадрата, построенные выше, и отличаются от них фрагментами, выделенными белым цветом.

 

Итак, можно составить программу по описанному алгоритму, которая построит 2304 магических квадрата 14-го порядка.

 

***

 

 

ПОСТРОЕНИЕ ГРУППЫ ПОПАРНО ОРТОГОНАЛЬНЫХ ДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ 15-го ПОРЯДКА

 

Для порядка 15 мне удалось построить не только одну пару ОДЛК, но целую группу попарно ортогональных диагональных латинских квадратов. Для этого построения я взяла известную группу MOLS 15-го порядка (см. статью http://www.natalimak1.narod.ru/mols15.htm ) и применила к латинским квадратам этой группы найденный метод, который описан выше. Сначала покажу группу MOLS 15-го порядка, состоящую из четырёх латинских квадратов (рис. 18 – 21) (копирую квадраты из указанной статьи).

 

Первый латинский квадрат

 

 

Рис. 18

 

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