Н. Макарова

 

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

 

КВАДРАТОВ ЧЕТЫРНАДЦАТОГО ПОРЯДКА

 

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

 

В книге Холла “Комбинаторика” (стр. 278 – 279) доказывается, что количество взаимно ортогональных латинских квадратов 14-го порядка (как и вообще любого порядка n = 4k + 2, k>1) не меньше 2. Тем самым опровергается гипотеза Эйлера, которая оказалась верной только для порядка 6.

 

В 1985 г. D. T. Todorov опубликовал статью“Three Mutually Orthogonal Latin Squares of Order 14” (Ars Combinatoria, 20 (1985), pp. 45-48). В этой статье рассказывается о составлении группы из трёх взаимно ортогональных латинских квадратов 14-го порядка. Эту статью я выложила здесь:

http://www.natalimak1.narod.ru/mk/mols14.pdf

 

Поскольку статья на английском языке, предлагаю хороший перевод статьи, который мне любезно сделала пользователь shwedka с форума http://dxdy.ru/

В этом переводе переводчица не писала формулы, даны ссылки на те места в тексте, где эти формулы записаны.

 

Перевод статьи Тодорова:

 

      Пусть N(n) означает максимальное количество взаимно ортогональных латинских квадратов размера n.

      Известно, что если n больше или равно 7, n не равно 10, 14, то N(n) больше или равно 3 [1,2].       Существование набора из s взаимно ортогональных ЛК размера n эквивалентно существованию ортогонального массива OA(n,s+2) [3]. Ортогональный массив OA(n,s) определяется как матрица (s x n²) над {1,..., n}, строки которой взаимно ортогональны, т.е., если

      r₁ = (x₁,....x_n^2), r₂ = (y₁,....y_n^2),

то любая пара (f,g) встречается ровно один раз среди пар (x_i, y_i). Ниже мы даем OA(14,5).

 

      Добавим точку * к полю Z₁₃ вычетов по модулю 13 и определим операции для a, принадлежащего Z₁₃: a + * = * + a = a* = *a = * (сложение и умножение подразумеваются по модулю 13).

 

      Пусть A = ||a_ij||, i=1,…,5, j=1,…,15 –  матрица над Z₁₃\cup *. Пусть

      r₁ = (x₁,...,x₁₅), r₂=(y₁,....y₁₅) – строки в А.

 

      Мы скажем, что они ортогональны, если

 

      1. (x_i, y_i) не равно (*,*)

 

      2. Существуют такие целые i₀, j₀ (i₀ не равно j₀; i₀, j₀ принадлежат [1,15]), что x_i0 = *, y_j0 = *

 

      3. Для любого a, принадлежащего Z_13, существует пара (x_i,y_i), такая что x_i - y_i = a.

 

      Матрица A называется DS-матрицей, если её строки взаимно ортогональны.

 

      Для любого b, принадлежащего Z₁₃, определим A + b = ||a_ij + b||.

      Очевидно, матрица

 

      (см. начало стр. 46)

 

      является ОА(14,5) - ортогональным массивом над Z₁₃\cup *.

 

      Очевидно, мы можем прибавить к любой строке целое число по модулю 13, так же, как к любому столбцу, не теряя DS свойство. Поэтому мы предположим, что первая строка А имеет вид

      (*, a, ... , a) для некоторого a, принадлежащего Z₁₃. Выбор этого a несуществен, так что мы удалим первую строку и первый столбец в А, обозначив оставшуюся матрицу (4х14) через AR. Очевидно,

 

      (1). Каждая строка в AR является перестановкой Z₁₃\cup *

      (2). Каждый столбец Z₁₃\cup * содержит различные элементы Z₁₃\cup *

      (3). Если r₁ = (x₁,..., x₁₄), r₂ = (y₁,... , y₁₄) – строки в AR, то для любого a, принадлежащего Z₁₃\{0}, найдётся ровно одна пара (x_i, y_i) такая что x_i  - y_i = a.

 

      Теперь предположим, что

 

      (формулы посередине стр. 46)

 

      – строки в AR. Поскольку А –  DS-матрица, то

 

      (формулы чуть ниже середины стр. 46)

 

      Поэтому

 

      (равенство двух сумм)

 

      С другой стороны,

 

      (формула с двумя суммами)

 

      согласно свойству (1). Поэтому \alpha = \beta.

 

      Поскольку A + b, bA – DS-матрицы для любого b принадлежащего Z₁₃\{0}, мы делаем вывод, что четыре столбца в AR представляют симметричную матрицу вида

 

      (матрица вверху стр. 47)

 

      Если проверить, то можно построить 375 различных матриц такого вида (заметим, что строки и столбцы в AR) можно переставлять.

 

      Ровно три из таких матриц удалось расширить до AR-матриц, что было получено путем вычислений на

      компьютере.

 

      (три толстых матрицы на стр. 47.)

 

Теперь осталось только разобраться, как же Тодоров строит свой ортогональный массив и как от ортогонального массива перейти к самим ортогональным квадратам. В конце статьи даны три матрицы размером 4х14. Никак не могу понять, как извлечь из этих матриц три взаимно ортогональных латинских квадрата 14-го порядка.

 

Сначала я взяла первую из этих матриц и достроила её до латинского квадрата 14-го порядка простым подбором. Надеялась, что мне удастся каким-нибудь способом построить второй латинский квадрат ортогональный построенному. Но ничего не получилось. Приведу этот самый латинский квадрат, построенный из первой матрицы 4х14, приведённой Тодоровым (рис. 1):

 

 

Рис. 1

 

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

 

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

 

 

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

 

 

Рис. 2

 

Увы, квадраты не получились ортогональными. Было сделано ещё множество попыток, но результат так и не достигнут.

 

Далее я попробовала составить пару ОЛК 14-го порядка по алгоритму, который разработала для порядков серии n = 4(mod 6). Вот что у меня получилось (рис. 3):

 

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

 

 

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

 

 

Рис. 3

 

И снова неудача – латинские квадраты не получаются ортогональными. Пробовала отразить первый латинский квадрат относительно горизонтальной (и вертикальной) оси симметрии, повернуть его на 90 градусов по часовой стрелке. Ортогональные квадраты не получаются!

 

Наконец, составила несколько латинских квадратов 14-го порядка, для которых ортогональный соквадрат тоже не нашла. Покажу и эти одиночные латинские квадраты. Вот, например, латинский квадрат, построенный по схеме Агриппы (рис. 4):

 

 

Рис. 4

 

Очень гармоничная схема составления этого латинского квадрата. Эта схема работает для любого чётного порядка.

На рис. 5 показан латинский квадрат, построенный по придуманной мной схеме.

 

 

Рис. 5

 

Интересно отметить, что данная схема работает для составления латинского квадрата любого порядка серии n = 4k + 2. Вот, например, латинский квадрат 10-го прядка, составленный по этой схеме (рис. 6):

 

 

Рис. 6

 

Однако и для этого латинского квадрата мне не удалось найти ортогональный соквадрат. Я пыталась это сделать с помощью перестановки строк в этом квадрате, но ничего из этого не получилось. Для квадратов 10-го порядка мне удалось найти в Интернете готовые пары ОЛК.

Латинский квадрат 6-го порядка тоже можно составить по данной схеме (рис. 7):

 

Рис. 7

 

Ну, для латинского квадрата 6-го порядка не надо искать ортогональный соквадрат, так как доказано, что он не существует.

 

Вот ещё одна пара латинских квадратов, уж и не помню, как построенная. Квадраты этой пары тоже не получились ортогональными. Смотрите рис. 8.

 

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

 

 

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

 

 

Рис. 8

 

Повторю, что я составила около двух десятков различных пар латинских квадратов 14-го порядка, но пару ортогональных квадратов мне найти не удалось.

 

Итак, задача поставлена. Задача имеет решение. Более того, оно уже готово. Не хватает ума разобраться. Может быть, мои читатели разберутся и мне подскажут, как же построить три взаимно ортогональных латинских квадрата 14-го порядка по статье Тодорова.

Ну, а далее у Тодорова есть статья о составлении четырёх взаимно ортогональных латинских квадратов 20-го порядка. В эту статью я ещё и не пыталась вникнуть. Надо сначала разобраться с порядком 14.

 

Напомню читателям, что из всех чётных порядков мне удалось разработать алгоритм составления пар ОЛК для следующих групп порядков: n = 6k, k>1 и n = 4(mod 6). Осталась группа порядков n = 2(mod 6), в которую как раз и входят порядки 14 и 20.

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

Но обо всём этом напишу позже, если удастся разобраться.

Очень надеюсь на вашу помощь, уважаемые читатели. Опубликовала задачу на форуме:

http://dxdy.ru/topic12959.html

 

но решения пока никто не дал.

 

25 января 2009 г.

г. Саратов

 

       Пишите мне!

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

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