ОРТОГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ ДЕСЯТОГО ПОРЯДКА

 

Данная страница является продолжением страницы

http://www.natalimak1.narod.ru/aspekty6.htm

 

 

Поскольку мои исследования в построении пар ортогональных латинских квадратов чётного порядка застопорились на группе порядков n = 2(mod 6), я решила написать отдельную статью об ортогональных латинских квадратах 10-го прядка. Для данного порядка найдено уже достаточно много пар ОЛК, есть даже три пары диагональных ОЛК. Не буду повторять здесь рассказ о гипотезе Л. Эйлера (1707 – 1783) и о том, как в 1958 году она была опровергнута Е. Т. Паркером, которому удалось найти греко-латинский квадрат 10-го порядка. Всё это подробно описано во многих источниках.

Замечу, что я буду представлять пару ОЛК не в виде греко-латинского квадрата, а в виде двух латинских квадратов. Так удобнее исследовать пару ОЛК. Для того чтобы ещё раз показать связь греко-латинского квадрата с парой ОЛК, приведу греко-латинский квадрат Паркера из книги М. Гарднера “Математические досуги” (М.: Мир, 1972) и представлю его в виде пары ОЛК. На рис. 1 вы видите греко-латинский квадрат Паркера.

 

 

Рис. 1

 

Прежде чем показать греко-латинский квадрат в виде двух ортогональных латинских квадратов, отмечу интересное свойство, которое отмечает и М. Гарднер в своей книге. Приведу цитату из книги:

 

 

На рис. 1 греко-латинский подквадрат 3-го порядка выделен жёлтым цветом.

 

А теперь показываю греко-латинский квадрат Паркера в виде двух ортогональных латинских квадратов (рис. 2):

 

 

Рис. 2

 

Греко-латинский квадрат получается из пары ортогональных латинских квадратов простым объединением элементов в соответствующих ячейках латинских квадратов. Понятие греко-латинского квадрата ввёл Эйлер, он обозначал элементы первого латинского квадрата буками греческого алфавита, а элементы второго латинского квадрата – буквами латинского алфавита. Иногда греко-латинский квадрат называют эйлеровским. Таким образом, греко-латинский квадрат – это более компактное представление пары ортогональных латинских квадратов.

Обратите внимание: греко-латинский квадрат 3-го порядка, находящийся в правом нижнем углу греко-латинского квадрата 10-го порядка, тоже разложился на пару ортогональных латинских квадратов 3-го порядка. На рис. 2 латинские квадраты 3-го порядка выделены жёлтым цветом.

 

***

 

Итак, в 1958-1959 гг. было составлено много пар ОЛК 10-го порядка. А пары диагональных ОЛК 10-го порядка были найдены только в 1992 г. Эти пары опубликованы в статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие). Покажу здесь ещё раз эти пары ОЛК (рис. 3 – 5).

 

 

Рис. 3

 

 

Рис. 4

 

 

Рис. 5

 

Пары диагональных ОЛК хороши тем, что они сразу пригодны для построения магического квадрата. Все латинские квадраты в парах диагональных ОЛК 10-го порядка являются нетрадиционными магическими квадратами с магической константой 45. Если составить из любой приведённой пары диагональных ОЛК греко-латинский квадрат, сразу получится магический квадрат 10-го порядка, записанный в нетрадиционном виде.

Кроме этих трёх пар мне больше не встречались пары диагональных ОЛК 10-го порядка.

 

***

 

Следующая группа ОЛК 10-го порядка найдена мной в статье, автором которой является Stenson (в других источниках я видела такое написание этой фамилии: Stinson; не знаю, как правильно). Эта группа задаётся в общем виде с применением трёх переменных. То есть мы имеем схему составления пар ОЛК. Варьируя значения переменных, можно составить шесть подобных пар ОЛК. На рис. 6 показана эта схема. Переменные a₁, a₂, a₃ могут принимать значения 7, 8, 9 в любой комбинации.

 

 

Рис. 6

 

Схема очень интересная. Она работает для любого порядка n = 10 (mod 12). Не буду подробно останавливаться на этой схеме, всё можно понять из раскраски латинских квадратов в данной паре ОЛК. Кроме того, я нашла аналогичную схему, о которой подробно рассказала в одной из предыдущих частей статьи. Эта схема приведена ниже.

Обратите внимание: и здесь в правом нижнем углу обоих латинских квадратов 10-го порядка находятся ортогональные латинские квадраты 3-го порядка.

 

***

 

В статье по ссылке http://www.mi.ras.ru/spm/pdf/011.pdf

(приведу здесь полностью титульный лист этой статьи:

 

Математический институт им. В. А. Стеклова

Российской Академии наук

Современные проблемы математики

Выпуск 11

(издание выходит с 2003 г.)

Конференция “Леонард Эйлер и современная математика”

      Сборник докладов

Москва. 2008)

 

найден очень интересный греко-латинский квадрат 10-го порядка. Разложив его на два ортогональных квадрата, я увидела, что в нём работает схема, аналогичная схеме Стенсона (рис. 6). Эта схема даже более изящная. Смотрите сами (рис. 7):

 

 

Рис. 7

 

Именно эта схема и послужила основой дальнейшей разработки алгоритма для порядков группы n = 4 (mod 6) (смотрите следующие части статьи: http://www.natalimak1.narod.ru/aspekty3.htm и http://www.natalimak1.narod.ru/aspekty4.htm ).

 

В латинских квадратах этих пар ОЛК тоже в правом нижнем углу находятся ортогональные квадраты 3-го порядка.

 

***

 

Наконец, покажу ещё одну пару ОЛК, полученную из греко-латинского квадрата, найденного в Интернете. К сожалению, не записала ссылку, но статью скопировала и приведу начало этой статьи:

 

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

ДЕСЯТОГО ПОРЯДКА

 

А. И. Лямзин

 

В 1959 г. Паркер [1] дал первый пример пары ортогональных латинских

квадратов порядка 10.

Латинским квадратом n-го порядка называется квадратная таблица

из п строк и п столбцов, ячейки которой заняты п различными элементами

так, что в любой строке и в любом столбце каждый из элементов

встречается один и только один раз. Два латинских квадрата одного

порядка называются ортогональными, если при их наложении каждая

из п² возможных упорядоченных пар элементов встречается один и только

один раз. Латинские квадраты и системы попарно ортогональных латинских

квадратов являются одним из инструментов исследования конечных

проективных плоскостей. Поиски пар ортогональных латинских квадратов

порядков вида 4n + 2 со времён Эйлера и до последнего времени

были безуспешными [2].

Автор этой статьи методом систематизированных проб, с учётом

закономерностей эмпирического характера, найденных из рассмотрения

пар ортогональных латинских квадратов более низких порядков, получил

другой пример:

 

00 11 22 33 44 55 66 77 88 99

12 05 50 86 39 24 73 98 61 47

23 58 06 60 97 41 35 84 19 72

34 83 69 07 70 18 52 46 95 21

45 32 94 71 08 80 29 63 57 16

56 27 43 15 82 09 90 31 74 68

67 79 38 54 26 93 01 10 42 85

78 96 81 49 65 37 14 02 20 53

89 64 17 92 51 76 48 25 03 30

91 40 75 28 13 62 87 59 36 04

 

Эта пара квадратов неизоморфна паре Паркера”.

 

А теперь покажу этот интереснейший греко-латинский квадрат в виде двух ортогональных латинских квадратов (рис. 8):

 

 

Рис. 8

 

Первый латинский квадрат в этой паре ОЛК обладает диагональной симметрией: в ячейках, симметрично расположенных относительно главной диагонали, выделенной зелёным цветом, находятся одинаковые числа. А второй латинский квадрат получается из первого перестановкой строк. Это первая пара ОЛК, обладающая таким свойством, из всех пар, которые мне удалось найти. Как уже отмечалось раньше, в группах взаимно ортогональных латинских квадратов порядков 7, 8 и 9 все квадраты получаются друг из друга перестановкой строк. А вот для квадратов 10-го порядка это редко встречается. Один товарищ писал мне, что это вообще вряд ли возможно для порядка 10. Оказалось, что возможно.

Ещё одна особенность этого греко-латинского квадрата: в нём отсутствует греко-латинский подквадрат 3-го порядка.

Я попробовала переставить точно так же столбцы в первом латинском квадрате и получила новую пару ОЛК (рис. 9).

 

 

Рис. 9

 

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

 

Как уже было сказано выше, пары не диагональных ОЛК в общем случае не пригодны для построения магических квадратов, так как латинские квадраты в этих парах ОЛК не являются нетрадиционными магическими квадратами, в них нет магической суммы чисел в диагоналях. Поэтому и возникла необходимость преобразования латинских квадратов в парах не диагональных ОЛК. Я использую два способа преобразований: 1) перестановка строк в латинских квадратах; 2) трансформация тождественной перестановки чисел. Покажу здесь оба способа применительно к парам ОЛК 10-го порядка.

 

ПЕРВЫЙ СПОСОБ ПРЕОБРАЗОВАНИЯ

 

Возьмём пару ОЛК с рис. 8. Преобразуем оба латинских квадрата в этой паре с помощью перестановки строк. Разумеется, строки переставляются в обоих квадратах одинаково. Получившаяся преобразованная пара ОЛК показана на рис. 10.

 

 

Рис. 10

 

В этой паре оба латинских квадрата являются нетрадиционными магическими квадратами с магической константой 45. Из данной пары строится такой магический квадрат (рис. 11):

 

 

Рис. 11

 

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

 

 

Рис. 12

 

Эти латинские квадраты обладают интересным свойством, которое позволяет построить из них магический квадрат. Обозначим S₁, S₂ – суммы чисел в диагоналях первого латинского квадрата, S₃, S₄ – суммы чисел в соответствующих диагоналях второго латинского квадрата. Имеем: S₁ = 46, S₂ = 45, S₃ = 35, S₄ = 45.  Очевидно, что неправильной в обоих латинских квадратах является одна и та же диагональ (то есть диагональ одного направления), и для этой неправильной диагонали выполняется равенство:

 

10*S₁ + S₃ + 1 = 505

 

Это и обеспечивает построение магического квадрата из данной пары ОЛК. На рис. 13 показан этот магический квадрат.

 

 

Рис. 13

 

Замечу, что в подобных парах ОЛК нельзя менять местами латинские квадраты в формуле для построения магического квадрата. Если поменять местами латинские квадраты в паре ОЛК с рис. 12, магический квадрат не получится.

 

ТРАНСФОРМАЦИЯ ТОЖДЕСТВЕННОЙ ПЕРЕСТАНОВКИ ЧИСЕЛ

 

Сначала рассмотрим преобразование, выполняемое с помощью трансформации тождественной перестановки чисел, на примере пары диагональных ОЛК Брауна с рис. 3.

Произведём такую замену тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

0  4  8  9  2  6  3  5  7  1

 

Преобразование выполняется просто: в обоих латинских квадратах надо заменить числа, выделенные красным цветом, на соответствующие числа (то есть подписанные под ними), выделенные синим цветом. Например: 1 à 4, 2 à 8 и т. д.

В результате такой замены получим следующую пару диагональных ОЛК (рис. 14):

 

 

Рис. 14

 

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

Легко убедиться, что ортогональность латинских квадратов при таком преобразовании сохраняется.

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

Рассмотрим частный случай преобразования, выполняемого с помощью трансформации тождественной перестановки чисел, – преобразование взятия дополнения. В качестве исходной пары ОЛК возьмём ту же пару с рис. 3. Преобразование взятия дополнения заключается в следующем: все числа в обоих латинских квадратах заменяются на их дополнение до 9, то есть число a заменяется на 9-a. Очевидно, что это преобразование равносильно следующей трансформации тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

9  8  7  6  5  4  3  2  1  0

 

На рис. 15 вы видите пару диагональных ОЛК, полученную данным преобразованием из пары ОЛК с рис. 3.

 

 

Рис. 15

 

А теперь рассмотрим трансформацию тождественной перестановки чисел для не диагональных пар ОЛК. В данном случае преобразование преследует определённую цель: получить в обеих диагоналях каждого латинского квадрата сумму чисел равную 45. Будем преобразовывать пару ОЛК Паркера, изображённую на рис. 2.

Начнём с преобразования первого латинского квадрата (на рис. 2 этот квадрат изображён слева). В этом латинском квадрате неправильная только одна диагональ. Для исправления этой диагонали достаточно применить такую трансформацию тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

2  1  0  6  4  5  3  7  8  9

 

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

 

0 à 2,   2 à 0,   3 à 6,   6 à 3

 

В результате такого преобразования получим следующий латинский квадрат (рис. 16):

 

 

Рис. 16

 

Очевидно, что этот латинский квадрат является нетрадиционным магическим квадратом с магической константой 45. Неправильная диагональ исправлена.

Переходим к преобразованию второго латинского квадрата (на рис. 2 этот квадрат изображён справа). В этом латинском квадрате обе диагонали неправильные. Поэтому выполняем преобразование в два этапа. Сначала исправляем диагональ

 

0  1  2  3  4  5  6  7  7  7

 

Сумма чисел в этой диагонали равна 42, до нужной суммы не хватает 3. Легко видеть, что следующая трансформация тождественной перестановки чисел исправит эту диагональ:

 

0  1  2  3  4  5  6  7  8  9

0  1  2  3  4  5  6  8  7  9

 

В результате такого преобразования получаем следующий латинский квадрат (рис. 17):

 

 

Рис. 17

 

Теперь надо исправить в полученном латинском квадрате вторую диагональ. Сумма чисел в этой диагонали равна 42. Выполним следующую трансформацию тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

0  2  3  1  4  5  6  7  8  9

 

В результате этого преобразования получаем латинский квадрат, в котором обе диагонали исправлены (рис. 18).

 

 

Рис. 18

 

Понятно, что два этапа преобразований можно объединить, сразу выполнив такую трансформацию тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9

0  2  3  1  4  5  6  8  7  9

 

И вот какой греко-латинский квадрат получен из греко-латинского квадрата Паркера (рис. 19):

 

 

Рис. 19

 

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

В предыдущих частях статьи было приведено несколько примеров преобразования с помощью тождественной перестановки чисел не только для латинских квадратов 10-го порядка. Я высказала предположение, что любой не диагональный латинский квадрат можно превратить с помощью такого преобразования в нетрадиционный магический квадрат, то есть добиться того, чтобы суммы чисел в диагоналях были равны суммам чисел в строках и столбцах. Однако найденная недавно пара ОЛК Лямзина опровергает это предположение. В самом деле, посмотрите на первый латинский квадрат в этой паре (дублирую) (рис. 20):

 

 

Рис. 20

 

Очевидно, что никакая трансформация тождественной перестановки чисел не может исправить диагональ, состоящую из нулей.

 

В предыдущих частях статьи было рассказано о группах взаимно ортогональных латинских квадратов 7-го, 8-го и 9-го порядков. Доказано, что для любого порядка n>=3, являющегося степенью простого числа, существует группа из n-1 попарно ортогональных латинских квадратов. Такая группа ортогональных квадратов называется полной.

С порядком 10 всё намного сложнее. До сих пор не найдено даже трёх попарно ортогональных латинских квадратов 10-го порядка. Посмотрите внимательно на три пары ОЛК Брауна (рис. 3 – 5). Вторые латинские квадраты в двух первых парах совершенно одинаковы. Однако первые латинские квадраты этих двух пар не ортогональны между собой.

Хорошая задача! В настоящей статье (считая все предыдущие её части) вы найдёте довольно много пар ОЛК 10-го порядка. Попробуйте построить такой латинский квадрат 10-го порядка, который будет ортогонален обоим квадратам какой-нибудь пары ОЛК.  Я проверила ортогональность всех имеющихся у меня латинских квадратов 10-го порядка и не нашла трёх взаимно ортогональных квадратов.

 

***

 

Вчера, бродя по Интернету в поисках информации об ортогональных латинских квадратах, нашла очень интересную книгу: Герберт Дж. Райзер. “Комбинаторная математика”, перевод К. А. Рыбникова, год издания, кажется, 1966.

В этой книге есть схема составления пары ортогональных латинских квадратов 10-го порядка. Вот эта схема (рис. 21):

 

 

Рис. 21

 

Сравните эту схему со схемой, изображённой на рис. 7. Вы увидите, что это та же самая схема. Отличия не принципиальны. Здесь латинские квадраты записаны в традиционном виде. Квадраты переставлены. И, наконец, в правом нижнем углу квадратов записана другая пара ортогональных латинских квадратов 3-го порядка. Здесь переменные x₁, x₂, x₃ принимают значения 7, 8, 9 в любой комбинации.

В книге тоже написано, что данная схема действует для любого порядка n = 10 (mod 12).

 

***

 

А эту пару ОЛК нашла в книге Холла “Комбинаторика” (см. рис. 22). В книге написано, что данную пару ОЛК составили Островский и Ван Дюрен с помощью ЭВМ.

 

 

Рис. 22

 

В заключение приведу найденную мной ссылку, по которой вы найдёте очень большой список литературы по теме ортогональных латинских квадратов:

 

http://citeseer.ist.psu.edu/old/colbourn99mutually.html

 

 

ДОБАВЛЕНИЕ (21 января 2009 г.)

 

Удивительную пару ОЛК составил Лямзин (см. рис. 8). Дублирую первый латинский квадрат этой пары (рис. 23).

 

 

Рис. 23

 

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

Посмотрите внимательно на структуру этого латинского квадрата. Закономерности очевидны. Достаточно найти набор чисел во второй строке, записанный правее числа 0. От каждого числа этого набора числа записываются параллельно главной диагонали по возрастанию; дойдя до 9, начинаем писать с числа 1 (смотрите раскраску на рис. 23). Очень изящная схема!

Рассмотрев внимательно эту схему, я подумала: а нет ли ещё латинского квадрата, составленного по такой же схеме? Конечно, написала программу, которая быстренько перебрала все возможные наборы чисел во второй строке квадрата. Программа выдала только два квадрата. Первый в точности совпадает с квадратом на рис. 23. А второй квадрат новый (рис. 24):

 

 

Рис. 24

 

Теперь переставляем строки в этом латинском квадрате точно так же, как это делается в паре ОЛК Лямзина (замечу, что программа выполняет это для каждого первого латинского квадрата, построенного по данной схеме, и в результате она выдала только те первые латинские квадраты, для которых перестановкой строк был получен ортогональный латинский квадрат). Второй латинский квадрат новой пары ОЛК вы видите на рис. 25.

 

 

Рис. 25

 

Теперь возникает такой вопрос: а не работает ли эта замечательная схема для других порядков, например, 12, 14 и т. д.? Чтобы это проверить, надо составить соответствующую программу. Вполне возможно, что по этой схеме удастся составить пару ОЛК 12 или 14 порядка. Или, может быть, 22-го порядка. Надо экспериментировать. Предлагаю читателям заняться этим прямо сейчас, а я займусь позже.

 

Продолжение читайте здесь:

 

http://www.natalimak1.narod.ru/olk.htm

 

16 - 21 января 2009 г.

г. Саратов

 

       Пишите мне!

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

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