Н. Макарова

 

НЕИЗОМОРФНЫЕ ПАРЫ ОРТОГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ

 

 

 

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

Понятно, что неизоморфные пары ОЛК не получаются друг из друга ни одним из преобразований указанного типа. Впервые я встретила термин “неизоморфная пара ортогональных латинских квадратов” в статье А. И. Лямзина, в которой приводится неизоморфная ранее известным пара ОЛК 10-го порядка. Эта пара тоже несколько раз была показана в моих статьях.

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

На рис. 1 – 2 вы видите данную пару ОЛК.

 

 

Рис. 1

 

 

Рис. 2

 

Символьные элементы a₁, a₂, a₃ принимают значения 10, 11, 0 в любой комбинации. На рис. 3 показана КРМ данной пары ОЛК в придуманной мной форме. Это очень удобная форма.

 

 

Рис. 3

 

Оказывается, выделенная секция КРМ может варьироваться! И при этом получаются неизоморфные пары ОЛК. Варьирование выполняется следующим образом: берутся все возможные перестановки в группах чисел 3, 5, 7 и 2, 3, 4. Здесь только две разные группы, в общем случае этих групп может быть четыре. Для каждой перестановки проверяется совместимость двух последних строк КРМ по известному критерию. Если вы внимательно посмотрите на латинские квадраты пары ОЛК, сразу поймёте, что варьирование выделенной секции КРМ равносильно перестановке строк в нижних прямоугольниках и перестановке столбцов в боковых прямоугольниках. Совершенно очевидно, что такие перестановки дают неизоморфные пары ОЛК.

Составив и выполнив программу варьирования секции КРМ, я получила 36 решений. Покажу первые 10 и последние 10 решений, вариант решения записывается в виде строки из четырёх групп чисел, следующих по порядку.

 

№ 1

 3  5  7  2  3  4  4  3  2  7  5  3

 2

 3  5  7  2  4  3  4  3  2  7  3  5

 3

 3  5  7  3  2  4  4  3  2  5  7  3

 4

 3  5  7  3  4  2  4  3  2  5  3  7

 5

 3  5  7  4  2  3  4  3  2  3  7  5

 № 6

 3  5  7  4  3  2  4  3  2  3  5  7

 7

 3  7  5  2  3  4  4  2  3  7  5  3

 8

 3  7  5  2  4  3  4  2  3  7  3  5

 9

 3  7  5  3  2  4  4  2  3  5  7  3

 10

 3  7  5  3  4  2  4  2  3  5  3  7

. . . . . . . . . . . . . . . . . . . . . . . . .

27

 7  3  5  3  2  4  2  4  3  5  7  3

 28

 7  3  5  3  4  2  2  4  3  5  3  7

 29

 7  3  5  4  2  3  2  4  3  3  7  5

 30

 7  3  5  4  3  2  2  4  3  3  5  7

 31

 7  5  3  2  3  4  2  3  4  7  5  3

 32

 7  5  3  2  4  3  2  3  4  7  3  5

 33

 7  5  3  3  2  4  2  3  4  5  7  3

 34

 7  5  3  3  4  2  2  3  4  5  3  7

 35

 7  5  3  4  2  3  2  3  4  3  7  5

 36

 7  5  3  4  3  2  2  3  4  3  5  7

 

Легко видеть, что показанной выше паре ОЛК соответствует решение № 6. А теперь покажу пару ОЛК, соответствующую решению № 1. Сначала показываю КРМ, соответствующую этому решению (рис. 4).

 

 

 

Рис. 4

 

На рис 5 – 6 вы видите пару ОЛК, построенную по данной КРМ.

 

 

Рис. 5

 

 

Рис. 6

 

Сравните эту пару ОЛК с парой ОЛК, показанной в начале статьи (рис. 1 – 2). Вы увидите, что эти две пары ОЛК отличаются только нижними прямоугольниками, в которых переставлены строки; в боковых прямоугольниках столбцы не переставлены в данном варианте решения.

Итак, мы имеем 36 неизоморфных пар ОЛК 12-го порядка.

 

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

 

Теперь перехожу к парам ОЛК 18-го порядка. Пары ОЛК данного порядка мне известны трёх видов: с латинским подквадратом 3х3, с латинским подквадратом 4х4 и с латинским подквадратом 5х5. Начну с последнего вида. Эта пара ОЛК построена мной по тому же самому алгоритму для серии порядков n = 6k, k > 1. На рис. 7 – 8 вы видите эту пару ОЛК.

 

 

 

Рис. 7

 

 

Рис. 8

 

Здесь символьные элементы a₁, a₂, a₃, a₄, a₅ принимают значения 14, 15, 16, 17, 0 в любой комбинации. Данная пара ОЛК имеет КРМ совершенно аналогичную показанной выше, смотрите эту КРМ на рис. 9.

 

 

Рис. 9

 

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

Сейчас составила программу варьирования выделенной секции КРМ, но опять же не полного варьирования, так как в этом случае программа будет выполняться очень долго, она будет содержать 20 вложенных циклов. Поэтому я ограничилась выбором решений, аналогичных показанному на рис. 9, в этом решении перестановки чисел в группах одинаковы в обеих строках КРМ. В таком неполном варианте программа выдала 240 решений. Покажу первые 10 и последние 10 решений.

 

 № 1

 3  5  7  9  11  5  6  4  3  2  5  6  4  3  2  3  5  7  9  11

 2

 3  5  7  9  11  6  4  5  3  2  6  4  5  3  2  3  5  7  9  11

 3

 3  5  7  11  9  5  6  4  2  3  5  6  4  2  3  3  5  7  11  9

 4

 3  5  7  11  9  6  4  5  2  3  6  4  5  2  3  3  5  7  11  9

 5

 3  5  9  7  11  5  6  3  4  2  5  6  3  4  2  3  5  9  7  11

 6

 3  5  9  7  11  6  4  3  5  2  6  4  3  5  2  3  5  9  7  11

 7

 3  5  9  11  7  5  6  3  2  4  5  6  3  2  4  3  5  9  11  7

 8

 3  5  9  11  7  6  4  3  2  5  6  4  3  2  5  3  5  9  11  7

 9

 3  5  11  7  9  5  6  2  4  3  5  6  2  4  3  3  5  11  7  9

 10

 3  5  11  7  9  6  4  2  5  3  6  4  2  5  3  3  5  11  7  9

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

231

 11  9  3  7  5  2  3  5  4  6  2  3  5  4  6  11  9  3  7  5

 232

 11  9  3  7  5  2  3  6  5  4  2  3  6  5  4  11  9  3  7  5

 233

 11  9  5  3  7  2  3  4  6  5  2  3  4  6  5  11  9  5  3  7

 234

 11  9  5  3  7  2  3  6  5  4  2  3  6  5  4  11  9  5  3  7

 235

 11  9  5  7  3  2  3  4  5  6  2  3  4  5  6  11  9  5  7  3

 236

 11  9  5  7  3  2  3  6  4  5  2  3  6  4  5  11  9  5  7  3

 237

 11  9  7  3  5  2  3  4  5  6  2  3  4  5  6  11  9  7  3  5

 238

 11  9  7  3  5  2  3  5  6  4  2  3  5  6  4  11  9  7  3  5

 239

 11  9  7  5  3  2  3  4  6  5  2  3  4  6  5  11  9  7  5  3

№ 240

11    9  7  5  3  2  3  5  4  6  2  3  5  4  6  11  9  7  5  3

 

Примечание: в данном примере перестановки чисел в группах получаются не только соответственные. Приведу пример такой перестановки. Изображаю варьируемые секции КРМ для решений № 1 и № 2. Хорошо видно, что не все пары чисел в столбцах этих двух секций одинаковы. Например, в первой секции имеем пары чисел 3, 5, и 5, 6, а во второй секции имеем пары чисел 3, 6 и 5, 4.. Однако группа разностей (по модулю 13) между числами в столбцах первой секции получается точно такая же, как группа разностей между числами в столбцах второй секции. Именно на этом свойстве основан рассматриваемый приём варьирования секции КРМ.

 

 

 

 

Очевидно, что КРМ с рис. 9 соответствует решению № 1. А теперь покажу КРМ, соответствующую решению № 240 (рис. 10).

 

 

Рис. 10

 

Строю пару ОЛК по данной КРМ (рис. 11 – 12). Чтобы затем проверить ортогональность построенных латинских квадратов, сразу заменяю в них символьные элементы конкретными числовыми значениями: a₁ = 14, a₂ = 15, a₃ = 16, a₄ = 17, a₅ = 0.

 

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

 

 

Рис. 11

 

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

 

 

Рис. 12

 

Программа проверки ортогональности подтверждает ортогональность этих латинских квадратов.

Итак, мы имеем 240 неизоморфных пар ОЛК 18-го порядка подобных паре, построенной мной по алгоритму для серии порядков n = 6k, k > 1. Но это ещё далеко не все пары ОЛК. По аналогии с парами ОЛК 12-го порядка логично предположить, что все четыре перестановки в секции КРМ могут быть различны. Предлагаю читателям составить программу полного перебора всех возможных вариантов, чтобы определить точное число решений.

Напомню, что в этом примере можно получать ещё неизоморфные пары ОЛК, варьируя пару ортогональных латинских подквадратов 5х5.

 

Второй вид пар ОЛК 18-го порядка был рассмотрен в статье “Ортогональные диагональные латинские квадраты” (http://www.natalimak1.narod.ru/diagon.htm ). В этой паре латинские квадраты сдержат латинский подквадрат 4х4. По программе я получила 2880 решений, дающих неизоморфные пары ОЛК. Причём все эти пары ОЛК легко превращаются в пары ортогональных диагональных латинских квадратов (ОДЛК).

Здесь есть интересный нюанс. Данная пара взята из группы MOLS 18-го порядка, состоящей из трёх квадратов. Значит, можно поставить задачу о нахождении неизоморфных групп MOLS на основе этой группы. Покажу КРМ данной группы MOLS (рис. 13).

 

 

Рис. 13

 

Понятно, что пятая строка в КРМ определяет третий латинский квадрат группы MOLS. А теперь показываю один из вариантов решения для пары ОЛК (рис. 14), этот вариант получен варьированием выделенной секции КРМ.

 

 

Рис. 14

 

К этой КРМ надо добавить пятую строку, совместимую с имеющимися четырьмя строками по известному критерию, и тогда будет получена новая неизоморфная группа MOLS 18-го порядка. Если вы сравните выделенные секции КРМ на рис. 13 и рис. 14, то увидите, что перестановки чисел здесь соответственные. Поэтому и для пятой строки тоже возьмём соответственную перестановку (рис. 15):

 

 

Рис. 15

Неизоморфная группа MOLS получена!

 

Осталось показать пары ОЛК третьего вида, в этой паре латинские квадраты содержат латинский подквадрат 3х3. Эта пара ОЛК построена по КРМ, приведённой в статье “The Existence of N₂ Resolvable Latin Squares” (A. J. Wolfe, A. C. H. Ling, J. H. Dinitz). На рис. 16 – 17 показана эта пара ОЛК.

 

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