Н. Макарова

 

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

 

 

Как я уже не раз писала, пары ортогональных диагональных латинских квадратов – это самый лучший вариант для метода латинских квадратов. В англоязычных статьях ортогональные диагональные латинские квадраты называются 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

 

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

           

 

Рис. 19

 

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

 

 

Рис. 20

 

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

 

 

Рис. 21

 

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

 

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

 

 

Рис. 22

 

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

 

 

Рис. 23

 

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

 

 

Рис. 24

 

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

 

 

Рис. 25

 

Понятно, что из этих попарно ортогональных латинских квадратов можно составить шесть пар ОДЛК. Из каждой пары ОДЛК методом латинских квадратов можно построить два магических квадрата. Образуем пару ОДЛК из первого и второго латинских квадратов. На рис. 26 – 27 показаны магические квадраты, построенные из образованной пары ОДЛК.

 

 

Рис. 26

 

 

Рис. 27

 

В этих магических квадратах одинакова одна главная диагональ.

 

Понятно, что каждый квадрат любой из шести пар ОДЛК может быть преобразован с помощью трансформации тождественной перестановки чисел. Таким образом, из каждого квадрата пары ОДЛК мы можем получить 15! (15 факториал) диагональных латинских квадратов, а из каждой пары ОДЛК получим 15!*15! пар ОДЛК. Но все эти пары будут изоморфные. А вот неизоморфных пар ОДЛК 15-го порядка мне пока не удалось получить. Очень надеюсь, что А. В. Назарок в своей статье построил как раз неизоморфную (построенным здесь парам) пару ОДЛК.

Кстати, ещё раз повторю просьбу помочь найти эту статью.

Повторю её данные:

Назарок А. В. Пары ортогональных дважды диагональных латинских квадратов порядков 15, 18 и 26. // Комбинаторный анализ. Вып. 32. М.: МГУ, 1989 г.

 

Заодно поищите статью: Heinrich K. and Hilton A. J. W. Doubly diagonal orthogonal Latin squares. // Discrete Math. Vol. 46. № 2. 1983.

 

***

 

ПОСТРОЕНИЕ ПАР ОДЛК 18-го ПОРЯДКА

 

Для построения пар ОДЛК 18-го порядка я взяла пару ОЛК из известной группы MOLS данного порядка, состоящей из трёх латинских квадратов. К сожалению, третий латинский квадрат этой группы не превращается в диагональный латинский квадрат. Построение группы MOLS 18-го порядка описано в статье http://www.natalimak1.narod.ru/mols18.htm

Копирую из этой статьи два первых латинских квадрата (рис. 28 – 29).

 

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

 

 

Рис. 28

 

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

 

 

Рис. 29

 

 

Сразу покажу КРМ этой пары ОЛК (рис. 30):

 

 

Рис. 30

 

Понятно, что символьные элементы a, b, c, d принимают значения 15, 16, 17, 18 в любой комбинации. В приведённых выше латинских квадратах символьные элементы заменены конкретными значениями.

Выделенная оранжевым цветом секция КРМ варьируется! Берутся перестановки чисел в группах 3, 4, 13, 14 и 5, 6, 7, 9. При этом проверяется совместимость третьей и четвёртой строк КРМ по известному критерию. Составленная мной программа выдала 2880 решений. Далее приводится КРМ решения № 2880 (рис. 31):

 

 

Рис. 31

 

На рис. 32 – 33 вы видите пару ОЛК, построенную по этой КРМ (символьные элементы заменены числовыми значениями: a = 15, b = 16, c = 17, d = 18).

 

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

 

 

Рис. 32

 

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

 

 

Рис. 33

 

Итак, мы имеем 2880 неизоморфных пар ОЛК 18-го порядка одинаковой структуры. Каждая из этих пар превращается в ОДЛК точно так, как было показано для ОДЛК 14-го и 15-го порядков. Сначала превращаю в ОДЛК пару ОЛК с рис. 28 – 29. Ортогональные диагональные латинские квадраты, полученные из этой пары ОЛК, представлены на рис. 34 – 35.

 

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

 

 

Рис. 34

 

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

 

 

Рис. 35

 

Первая пара ОДЛК 18-го порядка получена! Сразу построю из этой пары ОДЛК один магический квадрат методом латинских квадратов. На рис. 36 показан этот магический квадрат.

 

 

Рис. 36

 

Второй магический квадрат вы получите, поменяв местами латинские квадраты в формуле для построения магических квадратов.

 

А теперь превращаю латинские квадраты пары ОЛК решения № 2880 (с рис. 32 – 33) в диагональные и получаю новую неизоморфную пару ОДЛК. Вы видите эту пару ОДЛК на рис. 37 – 38.

 

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

 

 

Рис. 37

 

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

 

 

Рис. 38

 

Посмотрите на магический квадрат, построенный из этой пары ОДЛК (рис. 39).

 

 

Рис. 39

 

Этот магический квадрат отличается от магического квадрата с рис. 36 фрагментами, выделенными на рис. 39 белым цветом.

Следует отметить, что можно получать новые пары ОДЛК 18-го порядка, заменяя центральные латинские подквадраты 4х4 на любую другую пару ортогональных диагональных латинских квадратов 4-го порядка, состоящих из тех же элементов.

 

ДОБАВЛЕНИЕ (6 июня 2011 г.)

 

 

Недавно А. Чернов написал статью [1] о построении пары ОДЛК 12-го порядка. Он ссылается в статье на работу [2].

Я приведу здесь готовую пару ОДЛК 12-го порядка из статьи Чернова (рис. 40 - 41).

 

 

 

Рис. 40

 

 

Рис. 41

 

Вот теперь и эта пара ОДЛК известна. Осталась одна неизвестная мне пара ОДЛК – порядка 26.

На рис. 42 вы видите магический квадрат, построенный из этой пары ОДЛК методом латинских квадратов.

 

 

Рис. 42

 

Примечание. Написала небольшое приложение, в котором ещё несколько примеров построения пар ОДЛК порядка n = 3k, k – чётное. См. [3].

 

 

[1] А. Чернов. Ортогональные диагональные латинские квадраты. http://alexblack.wallst.ru/article.php?content=124

[2] Consolato Pellegrino and Paola Lancellotti. A New Construction Of Doubly Diagonal Orthogonal Latin Squares

            [3] Построение пар ОДЛК порядка 3k. http://www.natalimak1.narod.ru/ddolk.htm

 

 

16 –  21 апреля 2009 г. – 6 июня 2011 г.

г. Саратов

 

Читайте мою виртуальную книгу “Волшебный мир магических квадратов”:

 

http://www.klassikpoez.narod.ru/glavnaja.htm

 

Скачайте электронную версию этой книги:

 

http://narod.ru/disk/5834353000/Magic_squares.pdf.html

 

 

Заодно прихватите книгу “Позиционные системы счисления”, авось, пригодится:

 

http://narod.ru/disk/5936760000/pozic4.pdf.html

 

На главную страницу сайта:

http://www.klassikpoez.narod.ru/index.htm

 

На главную страницу раздела «Волшебный мир магических квадратов»

http://www.klassikpoez.narod.ru/glavnaja.htm

 

 

Контакты:

natalimak1@yandex.ru

QIP 571-379-327