Н. Макарова

 

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

 

 

 

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

Понятно, что неизоморфные пары ОЛК не получаются друг из друга ни одним из преобразований указанного типа. Впервые я встретила термин “неизоморфная пара ортогональных латинских квадратов” в статье А. И. Лямзина, в которой приводится неизоморфная ранее известным пара ОЛК 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 показана эта пара ОЛК.

 

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

 

 

Рис. 16 

 

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

 

 

Рис. 17

 

Понятно, что в этих латинских квадратах символьные элементы принимают значения 15, 16, 17 в любой комбинации.

На рис. 18 изображена КРМ данной пары ОЛК.

 

 

Рис. 18

 

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

 

№ 1

 0  7  11  4  5  10  7  4  14  3  6  5

 2

 0  7  11  4  10  5  7  4  14  3  5  6

 3

 0  7  11  5  4  10  7  4  14  6  3  5

 4

 0  7  11  5  10  4  7  4  14  6  5  3

 5

 0  7  11  10  4  5  7  4  14  5  3  6

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

32

 11  7  0  4  10  5  14  4  7  3  5  6

 33

 11  7  0  5  4  10  14  4  7  6  3  5

 34

 11  7  0  5  10  4  14  4  7  6  5  3

 35

 11  7  0  10  4  5  14  4  7  5  3  6

 № 36

 11  7  0  10  5  4  14  4  7  5  6  3

 

Примечание: в этом примере все перестановки соответственные.

 

Очевидно, что КРМ, изображённая на рис. 15, соответствует решению № 36. А теперь покажу КРМ, соответствующую решению № 1 (рис. 19).

 

 

Рис. 19

 

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

 

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

 

 

 Рис. 20

 

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

 

 

 Рис. 21

 

Покажу ещё одну подобную пару ОЛК – 24-го порядка. Эта пара тоже построена мной по алгоритму для серии порядков n = 6k, k > 1. Латинские квадраты этой пары содержат латинский подквадрат 7х7. Не буду показывать сами латинские квадраты этой пары, а покажу только её КРМ (рис. 22).

 

 

Рис. 22

 

При построении пары ОЛК по данному алгоритму выделенная секция КРМ получена по программе (но эта программа была составлена без использования КРМ). Тогда я ограничилась одним решением. Теперь составляю программу варьирования выделенной секции КРМ, при этом, как и в примере для пар ОЛК порядка 18, содержащих подквадрат 5х5, буду рассматривать только те случаи, когда перестановки групп чисел в обеих строках КРМ одинаковы; в КРМ на рис. 22 как раз такой случай. Читателям оставляю общий случай варьирования выделенной секции КРМ.

Составила программу и начала её выполнять. Пришлось прервать выполнение, потому что конца совсем не видно. Немудрено! Программе надо перебрать 25 401 600 вариантов. Прервала программу, когда было получено уже 1518 решений. Показываю первые 10 и последние 10 из полученных решений. В этом примере, конечно, перестановки получаются не только соответственные.

 

№ 1

 3  5  7  9  11  13  15  2  8  3  7  6  5  4

 2

 3  5  7  9  11  13  15  4  2  3  7  5  8  6

 3

 3  5  7  9  11  13  15  4  2  5  3  7  8  6

 4

 3  5  7  9  11  13  15  4  3  2  5  8  7  6

 5

 3  5  7  9  11  13  15  5  6  3  4  8  2  7

 6

 3  5  7  9  11  13  15  5  8  6  4  3  7  2

 7

 3  5  7  9  11  13  15  6  3  2  8  7  5  4

 8

 3  5  7  9  11  13  15  8  4  5  6  3  7  2

 9

 3  5  7  9  11  15  13  2  8  3  7  6  4  5

 10

 3  5  7  9  11  15  13  4  2  3  7  5  6  8

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

1509

 3  7  11  15  9  5  13  5  3  8  7  4  6  2

 1510

 3  7  11  15  9  5  13  5  6  3  2  4  8  7

 1511

 3  7  11  15  9  5  13  6  2  7  4  8  3  5

 1512

 3  7  11  15  9  5  13  8  5  3  2  6  4  7

 1513

 3  7  11  15  9  13  5  2  3  6  4  7  5  8

 1514

 3  7  11  15  9  13  5  4  2  8  6  5  7  3

 1515

 3  7  11  15  9  13  5  4  3  5  6  7  8  2

 1516

 3  7  11  15  9  13  5  4  5  7  6  3  8  2

 1517

 3  7  11  15  9  13  5  5  3  8  7  4  2  6

 № 1518

 3  7  11  15  9  13  5  5  6  3  2  4  7  8

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

 

Примечание: здесь каждая группа из семи чисел выведена один раз; в четвёртой строке КРМ эти группы чисел в точности повторяются.

 

Очевидно, что КРМ с рис. 22 соответствует решению № 1 (я тогда и выполняла программу до первого решения). А теперь покажу КРМ, соответствующую решению № 1518 (рис. 23).

 

 

Рис. 23

 

Предлагаю читателям построить пару ОЛК 24-го порядка по данной КРМ.

 

В заключение покажу знаменитую пару ОЛК 10-го порядка Паркера (пара приводится по книге М. Гарднера “Математические досуги” (М.: Мир, 1972). На рис. 24 вы видите КРМ пары ОЛК, а на рис. 25 саму пару.

 

 

Рис. 24

 

 

Рис. 25

 

Понятно, что здесь символьные элементы принимают значения 7, 8, 9 а любой комбинации.

Попробуем получить неизоморфные пары тем же самым приёмом – варьированием секции КРМ. В выделенной секции КРМ имеются только две разные группы чисел: 3, 5, 6 и 1, 2, 4. Составляю и выполняю программу варьирования секции КРМ. Программа выдала 108 решений! Показываю первые 21 решения.

 

№ 1

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

 2

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

 3

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

 4

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

 5

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

 6

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

 7

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

 8

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

 9

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

 10

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

 11

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

 12

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

 13

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

 14

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

 15

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

 16

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

 17

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

 18

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

 19

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

 20

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

№ 21

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

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

 

Очевидно, что КРМ с рис. 24 соответствует решению № 21. А теперь построим пару ОЛК, соответствующую решению № 1. На рис. 26 изображена КРМ этой пары ОЛК, а на рис. 27 сама пара ОЛК.

 

 

Рис. 26

 

Сравните эту КРМ с КРМ, изображённой на рис. 24. Вы увидите, что здесь перестановки чисел не соответственные. Поэтому и решений получилось 108, а не 36, как было бы в случае только соответственных перестановок. Замечательный пример: группы состоят из трёх чисел, при этом разных групп всего две (мало возможностей для варьирования), тем не менее, удалось получить не только соответственные перестановки.

 

 

Рис. 27

 

Таким образом, мы имеем 108 неизоморфных пар ОЛК 10-го порядка, построенных по схеме Паркера. Хорошую пару ОЛК построил Паркер! Заметьте: у этой пары юбилей – ей исполнилось 50 лет.изображена КРМ этой пары ОЛК, а на рис.  . . . . .

 

25 – 28 апреля 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

 

       Пишите мне!

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

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