Н. Макарова

 

НЕИЗОМОРФНЫЕ ГРУППЫ MOLS 18-го и 26-го ПОРЯДКА

 

 

В предыдущей статье показано построение неизоморфных пар ортогональных латинских квадратов (ОЛК). Для этого используется очень оригинальный приём варьирования секции квази-разностной матрицы (КРМ). Здесь я покажу построение неизоморфных групп MOLS 18-го и 26-го порядка таким же способом.

 

Начну с группы MOLS 18-го порядка, состоящей из трёх попарно ортогональных латинских квадратов (рис. 1 - 3).

 

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

 

 

Рис. 1

 

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

 

 

Рис. 2

 

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

 

 

Рис. 3

 

 

Построение этой группы MOLS описано в статье http://www.natalimak1.narod.ru/mols18.htm . Латинские квадраты группы обладают интересной симметрией. Они содержат латинский подквадрат 4х4.

Вот как выглядит КРМ этой группы MOLS в том виде, какой я получила по описанию, приведённому в книге “Handbook of Combinatorial Designs” (рис. 4):

 

 

Рис. 4

 

Символьные элементы x₁, x₂, x₃, x₄ принимают значения 15, 16, 17, 18 (или 15, 16, 17, 0) в любой комбинации. Если использовать первую группу значений, то латинские квадраты будут заполнены в нетрадиционной форме – числами от 1 до 18. Если использовать группу значений 15, 16, 17, 0, квадраты будут заполнены в традиционной форме – числами от 0 до 17.

 

А теперь преобразую КРМ к виду, придуманному мной. Именно в таком виде очень хорошо видно ту секцию КРМ, которую можно варьировать. Преобразованная КРМ показана на рис. 5.

 

 

Рис. 5

 

В этой КРМ выделена секция, в которой возможно варьирование групп чисел. При этом полностью сохранится симметрия латинских квадратов. Группы чисел, подвергаемых варьированию: 3, 4, 13, 14;  5, 6, 7, 9 и  1, 2, 9, 11. В третьей и четвёртой строках КРМ перестановки групп чисел берутся одинаковые, в пятой строке перестановка группы чисел берётся одна и та же. Разумеется, из всех возможных перестановок выбираются только те, которые не нарушают совместимость всех строк КРМ по известному критерию. Составив и выполнив программу, я получила 24 решения. Покажу все решения, ибо это очень интересный результат. Решения выводятся в виде выделенной секции КРМ.

 

№ 1                                        № 2                                       № 3                                        № 4

 3  4  13  14  7  6  5  9            3  4  14  13  7  6  9  5             3  13  4  14  7  5  6  9             3  13  14  4  7  5  9  6

 7  6  5  9  3  4  13  14            7  6  9  5  3  4  14  13             7  5  6  9  3  13  4  14             7  5  9  6  3  13  14  4

            2  11  9  1  2  11  9  1             2  11  1  9  2  11  1  9             2  9  11  1  2  9  11  1             2  9  1  11  2  9  1  11

 

№ 5                                        № 6                                        № 7                                        № 8

            3  14  4  13  7  9  6  5             3  14  13  4  7  9  5  6             4  3  13  14  6  7  5  9             4  3  14  13  6  7  9  5 

            7  9  6  5  3  14  4  13             7  9  5  6  3  14  13  4             6  7  5  9  4  3  13  14             6  7  9  5  4  3  14  13   

 2  1  11  9  2  1  11  9            2  1  9  11  2  1  9  11             11  2  9  1  11  2  9  1             11  2  1  9  11  2  1  9    

 

№ 9                                        № 10                                     № 11                                      № 12

 4  13  3  14  6  5  7  9            4  13  14  3  6  5  9  7            4  14  3  13  6  9  7  5             4  14  13  3  6  9  5  7

 6  5  7  9  4  13  3  14            6  5  9  7  4  13  14  3            6  9  7  5  4  14  3  13             6  9  5  7  4  14  13  3

 11  9  2  1  11  9  2  1            11  9  1  2  11  9  1  2             11  1  2  9  11  1  2  9             11  1  9  2  11  1  9  2   

 

№ 13                                      № 14                                     № 15                                      № 16

 13  3  4  14  5  7  6  9            13  3  14  4  5  7  9  6             13  4  3  14  5  6  7  9             13  4  14  3  5  6  9  7    

 5  7  6  9  13  3  4  14            5  7  9  6  13  3  14  4             5  6  7  9  13  4  3  14             5  6  9  7  13  4  14  3    

 9  2  11  1  9  2  11  1            9  2  1  11  9  2  1  11             9  11  2  1  9  11  2  1             9  11  1  2  9  11  1  2

 

№ 17                                      № 18                                      № 19                                     № 20

 13  14  3  4  5  9  7  6            13  14  4  3  5  9  6  7             14  3  4  13  9  7  6  5             14  3  13  4  9  7  5  6

 5  9  7  6  13  14  3  4            5  9  6  7  13  14  4  3             9  7  6  5  14  3  4  13             9  7  5  6  14  3  13  4

 9  1  2  11  9  1  2  11            9  1  11  2  9  1  11  2             1  2  11  9  1  2  11  9             1  2  9  11  1  2  9  11

 

№ 21                                      № 22                                      № 23                                      № 24  

 14  4  3  13  9  6  7  5            14  4  13  3  9  6  5  7             14  13  3  4  9  5  7  6             14  13  4  3  9  5  6  7

 9  6  7  5  14  4  3  13            9  6  5  7  14  4  13  3             9  5  7  6  14  13  3  4             9  5  6  7  14  13  4  3

 1  11  2  9  1  11  2  9            1  11  9  2  1  11  9  2             1  9  2  11  1  9  2  11             1  9  11  2  1  9  11  2

 

Примечание: все перестановки в данном примере соответственные. Определение соответственных перестановок смотрите в предыдущей статье “Неизоморфные пары ортогональных латинских квадратов”.

 

Очевидно, что КРМ, изображённая на рис. 5, соответствует решению № 22.

А теперь покажу решение № 1. Сначала КРМ (рис. 6), а затем группу MOLS (рис. 7 – 9). В латинских квадратах группы символьные элементы заменены конкретными числовыми значениями: x₁ = 15, x₂ = 16, x₃ = 17, x₄ = 18.

 

Квази-разностная матрица (решение № 1)

 

 

Рис. 6

 

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

 

 

Рис. 7

 

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

 

 

Рис. 8

 

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

 

 

Рис. 9

 

Понятно, что очень легко запрограммировать получение всех 24 вариантов КРМ, а по КРМ и построение групп MOLS.

Заметьте, что из данной группы MOLS можно получать неизоморфные группы и другим способом: варьируя латинские подквадраты 4х4.

Напомню, что именно на основе этой группы MOLS я получила 2880 неизоморфных пар ортогональных диагональных латинских квадратов (ОДЛК) (см. статью http://www.natalimak1.narod.ru/diagon.htm ).

 

 

Перехожу к группе MOLS 26-го порядка. Эта группа также построена по книге “Handbook of Combinatorial Designs”.

На рис. 10 изображена квази-разностная матрица, построенная из матрицы, приведённой в книге.

 

 

Рис. 10

 

Здесь символьные элементы x₁, x₂, x₃, x₄, x₅ принимают значения 22, 23, 24, 25, 26  (или 22, 23, 24, 25, 0) в любой комбинации.

                        Построение группы MOLS по данной КРМ смотрите в статье http://www.natalimak1.narod.ru/mols26_38.htm

Теперь хочу применить к этой группе MOLS тот же самый приём варьирования секции КРМ. Сначала преобразую КРМ к виду, удобному для применения этого приёма (рис. 11):

 

 

Рис. 11

 

В этом примере надо варьировать восемь различных групп, каждая из которых состоит из 5 чисел. Я перечислю эти группы:

 

2,    7,    8,    9,  15

3,  10,  17,  18,  20

4,  11,  12,  19,  21

3,   9,   13,  18,  19

2,   6,     7,  11,  15

7,   9,   14,  16,  21

3,   5,     6,  13,  20

3,   4,   10,  11,  13

 

Совершенно понятно, что сразу можно применить все соответственные перестановки. Я составила программу для таких перестановок и получила 14400 решений. Это тоже вполне понятно: каждая группа из пяти чисел в третьей строке КРМ имеет 120 вариантов. Группы чисел в остальных строках КРМ располагаются соответственно группам чисел в третьей строке КРМ. Вот один пример КРМ с соответственными перестановками (рис. 12):

 

 

Рис. 12

 

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

Сложнее в этом примере найти не соответственные перестановки. Мне удалось найти только одну такую перестановку, да и то не для всей КРМ, а только для первых четырёх строк. Таким образом, я получила 14400 новых вариантов неизоморфных пар ОЛК. На рис. 13 показана КРМ с не соответственной перестановкой.

 

 

Рис. 13

 

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

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

Чтобы решить эту задачу полностью, надо придумать какую-то оптимизацию, потому что решение задачи в лоб вряд ли возможно за приемлемое время. Судите сами: количество всех возможных перестановок в восьми группах, состоящих из пяти чисел, равно 120⁸.

 

В заключение покажу пару ОЛК 26-го порядка, построенную по КРМ, изображённой на рис. 13 (рис. 14 – 15). В латинских квадратах символьные элементы заменены конкретными числовыми значениями: x₁ = 22, x₂ = 23, x₃ = 24, x₄ = 25, x₅ = 26.

 

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

 

 

Рис. 14

 

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

 

 

Рис. 15

 

 

***

 

Составила на досуге программки для каждой из оставшихся пар ОЛК из рассматриваемой группы MOLS. Не соответственная перестановка нашлась только одна. Вот она (рис. 16):

 

 

Рис. 16

 

Мы имеем ещё 14400 новых неизоморфных пар ОЛК 26-го порядка. К этой паре ОЛК тоже не удалось добавить ортогональные квадраты.

Пара ОЛК, построенная по КРМ, изображённой на рис. 16, показана на рис. 17 – 18.

 

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

 

 

Рис. 17

 

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

 

 

Рис. 18

 

 

 

 

29 - 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

 

       Пишите мне!

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

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