Н. Макарова

 

ПОСТРОЕНИЕ ГРУПП MOLS ЧЕТЫРНАДЦАТОГО ПОРЯДКА

 

В статье “Построение ортогональных латинских квадратов из ортогонального массива” (http://www.natalimak1.narod.ru/arry.htm ) было показано построение пары ОЛК 14-го порядка по описанию, приведённому в книге М. Холла. Здесь будет показано построение групп взаимно ортогональных латинских квадратов 14-го порядка, состоящих из трёх квадратов. При написании статьи использовалась следующая литература:

[1] “Handbook of Combinatorial Designs” (издание 1996 г.);

[2] “Handbook of Combinatorial Designs” (издание 2007 г.);

[3] D. T. Todorov. “Three Mutually Orthogonal Latin Squares of Order 14”;

[4] Stinson. 6. Latin Squares (видимо, глава из какой-то книги).

Кроме того, хочу выразить благодарность участникам форума http://dxdy.ru/topic12959.html за данные разъяснения, с помощью которых мне удалось построить все группы MOLS 14-го порядка, приведённые в настоящей статье.

Сразу отмечу, что все построенные здесь латинские квадраты записаны в нетрадиционной форме, то есть заполнены числами от 1 до 14. Чтобы привести их к традиционной форме записи (заполнить числами от 0 до 13), надо просто уменьшить все элементы в приведённых латинских квадратах на единицу.

 

Начну с группы MOLS 14-го порядка, приведённой в [1]. Я не буду использовать символьные элементы a, b, c, d, e, как это сделано в книге, а заполню квадраты числами от 1 до 14. Мне совершенно непонятно, зачем авторы ввели эти символьные элементы, поэтому я их просто заменяю числами. На рис. 1 – 3 вы видите эту группу MOLS.

 

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

 

 

Рис. 1

 

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

 

 

Рис. 2

 

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

 

 

Рис. 3

 

Поскольку эта группа приведена в книге в явном виде, я не знаю, по какому алгоритму она построена.

 

Примечание: смотрите Добавление в конце данной статьи.

 

В [2] группа MOLS 14-го порядка строится по так называемой квази-разностной матрице (quasi-difference matrix). Это как раз матрица подобная приведённой в статье Тодорова. После разъяснений на форуме, мне стало понятно, как строить группу MOLS по такой матрице. Сначала покажу квази-разностную матрицу из [2] (рис. 4).

 

 

Рис. 4

 

Примечание: все элементы матрицы увеличены на единицу, потому что латинские квадраты я буду заполнять числами от 1 до 14, как и в группе, показанной выше.

 

Как строить латинские квадраты по этой квази-разностной матрице, опишу кратко и покажу наглядно на построении первого латинского квадрата (рис. 5). Первый две строки в квази-разностной матрице – это координаты или иными словами – номера строк и столбцов в латинских квадратах. Теперь берём, например, первый столбец матрицы; имеем: в первой строке и пятом столбце (1,5) в первом латинском квадрате запишем число 5, во втором латинском квадрате – число 11, в третьем латинском квадрате – число 6. Прочерк означает последнюю строку, последний столбец или число 14 (соответственно). От записанных в ячейки чисел заполнение идёт по диагонали вправо и вниз, числа пишутся в порядке возрастания, после числа 13 пишется число 1. Такое заполнение происходит в квадрате 13х13, последняя строка и последний столбец в этом не участвуют. При достижении краёв квадрата 13х13 происходит переход на другую сторону квадрата, как если бы этот квадрат был свёрнут в трубочку по горизонтальной или вертикальной оси. Всё это очень похоже на то, как строятся латинские квадраты по ортогональному массиву (см. указанную выше статью). На рис. 5 перед квадратом и над квадратом приведены номера строк и столбцов, чтобы было хорошо видно, в какие ячейки вписываются числа из квази-разностной матрицы. Ячейки с числами из квази-разностной матрицы выделены жёлтым цветом. В последней строке и последнем столбце вписано по одному числу. далее заполнение идёт от вписанного числа по возрастанию с таким же зацикливанием после числа 13.

 

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

 

 

Рис. 5

 

Примечание: следует отметить, что можно первую и вторую координаты – номер строки и столбца – рассматривать в обратном порядке, то есть первое число в столбце квази-разностной матрицы считать номером столбца, а второе число – номером строки. На рис. 6 показан первый латинский квадрат, построенный в такой системе координат.

 

 

Рис. 6

 

Очевидно, что полученный в этом случае латинский квадрат эквивалентен квадрату с рис. 5, он получается из него отражением относительно главной диагонали.

 

Совершенно аналогично строятся второй и третий латинские квадраты. На рис. 7 – 8 показаны эти квадраты без подробностей построения.

 

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

 

 

Рис. 7

 

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

 

 

Рис. 8

 

Легко видеть, что две приведённые группы MOLS 14-го порядка не изоморфны.

Теперь перехожу к построению групп по квази-разностным матрицам, приведённым в [3]. Я долго на могла построить эти группы, потому что не знала, как надо по квази-разностной матрице строить сами ортогональные латинские квадраты. На рис.  9 показываю первую квази-разностную матрицу Тодорова.

 

 

Рис. 9

 

Примечание: во всех квази-разностных матрицах Тодорова тоже все элементы увеличены на единицу.

 

На рис. 10 показано подробное построение первого латинского квадрат 14-го порядка по данной матрице. Во всех построениях по матрицам Тодорова система координат выбрана так: первая координата (x) – номер столбца, вторая координата (y) – номер строки. Положительная полуось x направлена вправо, положительная полуось y направлена вниз. Жёлтым цветом выделены ячейки, содержащие числа из квази-разностной матрицы.

 

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

 

 

Рис. 10

 

На рис. 11 – 12 вы видите второй и третий латинские квадраты из данной группы MOLS.

 

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

 

 

Рис. 11

 

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

 

 

Рис. 12

 

Это третья группа, не являющаяся изоморфной двум группам из [1] и [2].

Тодоров привёл в своей статье три квази-разностные матрицы, которые содержат подматрицу 4х4, имеющую одинаковую структуру. На рис. 13 показана вторая квази-разностная матрица Тодорова. Одинаковая подматрица выделена зелёным цветом. В статье написано, что можно составить 375 различных квази-разностных матриц, содержащих такую подматрицу. Это легко сделать с помощью компьютера. Понятно, что каждая такая квази-разностная матрица даст новую группу MOLS.

 

 

Рис. 13

 

На рис. 14 показано построение первого латинского квадрата по данной матрице.

 

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

 

 

Рис. 14

 

На рис. 15 – 16 показаны второй и третий латинские квадраты из этой группы.

 

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

 

 

Рис. 15

 

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

 

 

Рис. 16

 

Наконец, последняя квази-разностная матрица Тодорова показана на рис. 17.

 

 

Рис. 17

 

На рис. 18 вы видите построение первого латинского квадрата по данной матрице.

 

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

 

 

Рис. 18

 

На рис. 19 – 20 показаны ещё два латинских квадрата этой группы MOLS.

 

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

 

 

Рис. 19

 

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

 

 

Рис. 20

 

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

Хорошая задача для читателей: составить программу для нахождения всех квази-разностных матриц, содержащих подматрицу 4х4, построенную Тодоровым. Как следует из статьи Тодорова, таких матриц должно быть 375.

 

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

 

В заключение покажу очень интересную пару ОЛК 14-го порядка, построенную по квази-разностной матрице, найденной в [4]. В этой паре полная аналогия с парой ОЛК 10-го порядка, алгоритм построения которой показан в одной из статей цикла “Новые аспекты метода латинских квадратов”.

На рис. 21 приведена квази-разностная матрица из [4] (все элементы матрицы увеличены на единицу).

 

 

Рис. 21

 

На рис. 22 вы видите подробное построение (с осями координат) первого латинского квадрата по данной матрице.

 

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

 

 

Рис. 20

 

На рис. 21 показан второй латинский квадрат.

 

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

 

 

Рис. 21

 

Понятно, что переменные x₁, x₂, x₃ могут принимать значения 12, 13, 14 в любой комбинации. Кроме того, эти переменные задают подквадраты 3-го порядка, которые тоже можно варьировать, и это даст существенно новые (неизоморфные) пары ОЛК. Приведу одну пару ОЛК с конкретными значениями переменных: x₁ = 12, x₂ = 13, x₃ = 14 (рис. 22 – 23).

 

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

 

 

Рис. 22

 

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

 

 

Рис. 23

 

 

25 - 26 февраля 2009 г.

г. Саратов

 

 

ДОБАВЛЕНИЕ

 

 

Поработав с квази-разностными матрицами и написав цикл статей “Подробно о квази-разностной матрице”, я поняла, что группа MOLS 14-го порядка из книги “Handbook of Combinatorial Designs”, приведённая в самом начале этой статьи (рис. 1 – 3), тоже построена по квази-разностной матрице. Я немного преобразовала латинские квадраты этой группы MOLS. На рис. 24 – 26 вы видите эту группу MOLS в преобразованном виде.

 

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

 

 

Рис. 24

 

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

 

 

Рис. 25

 

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

 

 

Рис. 26

 

А теперь покажу квази-разностную матрицу этой группы MOLS (рис. 27):

 

 

Рис. 27

 

Примечание: элементы в КРМ даны для традиционно заполненных латинских квадратов. Символьный элемент a равен 13. Чтобы привести латинские квадраты в соответствие с КРМ, надо уменьшить все их элементы на единицу.

 

Таким образом, мы имеем ещё одну группу MOLS из латинских квадратов, содержащих подквадрат 1х1. Читайте о таких группах MOLS в цикле статей “Подробно о квази-разностной матрице”. Первая статья этого цикла: http://www.natalimak1.narod.ru/quazi.htm

 

 

30 марта 2009 г.

г. Саратов.

 

 

 

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

 

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

 

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

 

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

 

 

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

 

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

 

       Пишите мне!

Приглашаю всех на форум!

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