Н. Макарова

 

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

 

 

Здесь рассмотрены некоторые схемы построения классических латинских квадратов. При этом латинские квадраты будем представлять в символьном виде, то есть заполнять их не числами 1, 2, 3, …, n, а символьными элементами a₁, a₂, a₃, …, a_n. Понятно, что от символьного латинского квадрата очень легко перейти к латинскому квадрату, заполненному числами, присвоив символьным элементам числовые значения 1, 2, 3, … , n (или 0, 1, 2, … , n – 1) в любой комбинации. Все латинские квадраты, получаемые варьированием значений символьных элементов, будут изоморфными. Можно сказать, что эти квадраты получаются друг из друга преобразованием, которое я назвала трансформацией тождественной перестановки чисел. Понятно, что группа получаемых таким преобразованием изоморфных латинский квадратов будет содержать n! квадратов.

 

 

ЦИКЛИЧЕСКИЙ СДВИГ

 

Циклический сдвиг – очень простая схема построения латинских квадратов. Она работает для латинских квадратов любого порядка. Каждая следующая строка (или каждый следующий столбец) латинского квадрата получается из предыдущей строки (или столбца) циклическим сдвигом с постоянным шагом k. Для квадрата порядка n шаг k может быть таким, что у k нет общих делителей с n, кроме 1.

Интересно отметить, что для порядков, являющихся простым числом, этим методом строится полная группа взаимно ортогональных латинских квадратов.

 На рис. 1 – 5 вы видите латинские квадраты порядков 2 - 6, построенные данным методом.

 

 

Рис. 1

 

 

Рис. 2

 

 

Рис. 3

 

 

Рис. 4

 

 

Рис. 5

 

Для порядков 3 и 5 получились полные группы MOLS. Понятно, что квадраты 4-го порядка (а тем более – 6-го порядка) не ортогональны.

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

 

Покажу ещё одну схему циклического сдвига, когда циклически сдвигаются блоки 2х2. Таким методом строятся латинские квадраты, состоящие из латинских подквадратов 2х2. По приведённым конкретным примерам легко понять, как работает данная схема. Для большей наглядности латинские квадраты заполнены числами. На рис. 6 показан латинский квадрат 6-го порядка, на рис. 7 – латинский квадрат 8-го порядка, на рис. 8 – латинский квадрат 20-го порядка. Понятно, что данный метод применим для построения латинских квадратов чётных порядков n > 2.

 

 

Рис. 6

 

 

Рис. 7

 

 

Рис. 8

 

 

В символьном виде латинский квадрат с рис. 6 будет выглядеть так (рис. 8а):

 

 

Рис. 8а

 

 

АЛГОРИТМ АГРИППЫ

 

Алгоритм Агриппы применяется для построения латинских квадратов любого чётного порядка n > 2. Я получила этот алгоритм, разложив на пару ортогональных латинских квадратов известный полумагический квадрат 12-го порядка, автором которого является Агриппа. К сожалению, второй латинский квадрат в этой паре ОЛК является обобщённым латинским квадратом. Начну демонстрацию алгоритма Агриппы с латинского квадрата 4-го порядка (рис. 9).

 

 

Рис. 9

 

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

На рис. 10 показываю латинский квадрат 6-го порядка, построенный по этому алгоритму.

 

 

Рис. 10

 

Теперь, думаю, схема стала совсем понятна. Здесь в четвёртой строке производится циклический сдвиг с шагом 4. Соответственно в латинском квадрате 8-го порядка в шестой строке производится циклический сдвиг с шагом 6, в латинском квадрате 10-го порядка в восьмой строке производится циклический сдвиг с шагом 8 и так далее.

Покажу ещё два примера – латинские квадраты 8-го и 10-го порядка (рис. 11 – 12).

 

 

Рис. 11

 

 

Рис. 12

 

Во всех латинских квадратах (рис. 9 – 12) оранжевым цветом выделены строки, содержащие перестановку предыдущей строки, записанную в обратном порядке.

Вот как выглядит нормализованный латинский квадрат с рис. 12 (рис. 13):

 

 

 

Рис. 13

 

 

ПОСТРОЕНИЕ С ПОМОЩЬЮ КВАЗИ-РАЗНОСТНОЙ МАТРИЦЫ

 

Метод построения латинских квадратов с помощью квази-разностной матрицы (КРМ) подробно описан в статье http://www.natalimak1.narod.ru/quazi.htm . Сначала я разработала свою схему построения латинского квадрата любого чётного порядка n > 2, когда ещё не знала о КРМ. Потом увидела, что к этой схеме можно применить КРМ. Покажу здесь латинский квадрат 8-го порядка, построенный по этой схеме (рис. 14).

 

 

Рис. 14

 

На рис. 15 изображена КРМ этого латинского квадрата.

 

 

Рис. 15

 

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

 

0  1  2  3  4  5  6  7

1  2  3  4  5  6  7  0

 

На рис. 16 вы видите преобразованный латинский квадрат. Он изоморфен латинскому квадрату с рис. 14.

 

 

Рис. 16

 

Все латинские квадраты, построенные по этой схеме, содержат подквадрат 1х1 и имеют определённую структуру, КРМ этих латинских квадратов тоже подобны; можно составить КРМ в общем виде для любого чётного порядка n > 2.

 

Найденная мной в Интернете пара ОЛК 10-го порядка, автором которой является А. И. Лямзин, тоже состоит из латинских квадратов, построенных по описанной схеме. Эти латинские квадраты тоже содержат подквадрат 1х1 и имеют такую же структуру. Подробно схема Лямзина описана в указанной статье. Здесь покажу латинские квадраты 10-го, 12-го и 14-го порядков, построенные по схеме Лямзина (рис. 17 - 19).

 

 

Рис. 17

 

 

Рис. 18

 

 

Рис. 19

 

Эти латинские квадраты интересны тем, что они симметричны относительно главной диагонали.

Для квадратов этой группы так же возможно построение изоморфных латинских квадратов, как это было показано для предыдущей группы квадратов. Для порядка 10 мне удалось найти неизоморфный латинский квадрат такой же структуры (по программе). Вы видите этот квадрат на рис. 20.

 

 

Рис. 20

 

Для латинских квадратов 4-го, 8-го и 10-го порядков, построенных по схеме Лямзина, существуют ортогональные соквадраты. Существуют ли ортогональные соквадраты для следующих чётных порядков, я не выяснила. Этот вопрос остаётся открытым. Хорошая задача для читателей!

 

Работая с КРМ, я нашла ещё одну интересную схему построения латинских квадратов для любого чётного порядка n > 2. Покажу латинские квадраты, построенные по этой схеме, для порядков 4 – 12 (рис. 21 – 22).

 

 

Рис. 21

 

 

 

Рис. 22

 

Помимо того, что схема расположения чисел в этих латинских квадратах очень изящная, эти квадраты обладают интересным свойством: они являются нетрадиционными магическими квадратами, то есть в них сумма чисел в обеих главных диагоналях равна магической константе квадрата, хотя диагональными они не являются (кроме квадрата 4-го порядка). В одной главной диагонали этих квадратов все элементы различны. А в другой главной диагонали содержится набор таких чисел: 0, 1, n – 1 и n/2 (n – 3) раза. Сумма этих чисел равна:

 

1 + n – 1 + (n – 3)*n/2 = n*(n – 1)/2

 

К сожалению, ортогональный соквадрат мне удалось построить только для порядка 4. Покажу оба квадрата данной пары ОЛК (рис. 23):

 

 

Рис. 23

 

Для порядков, начиная с 8, нахождение ортогонального соквадрата – сложная задача, но её стоит решать. Если удастся найти ортогональные соквадраты для всех латинских квадратов данной группы, которые тоже будут являться нетрадиционными магическими квадратами, то мы получим уникальный алгоритм, дающий нам пары ОЛК любого чётного порядка (кроме 2 и 6), сразу пригодные для построения магических квадратов.

 

Не буду описывать здесь метод составных квадратов, который был описан в статьях: “Построение пар диагональных латинских квадратов методом составных квадратов” (http://www.natalimak1.narod.ru/aspekty5.htm ) и “Построение пар ортогональных латинских квадратов методом составных квадратов” (http://www.natalimak1.narod.ru/olk.htm ).

 

В заключение покажу построение латинских квадратов нечётного порядка не кратного 3 методом циклического сдвига. Эти латинские квадраты замечательны тем, что они являются нетрадиционными магическими квадратами, обладающими свойством ассоциативности и пандиагональности и, кроме того, для этих латинских квадратов существуют ортогональные соквадраты, обладающие такими же свойствами. Таким образом, мы имеем замечательные пары ОЛК, из которых строятся методом латинских квадратов идеальные магические квадраты. Подробно смотрите об этом в статье http://www.natalimak1.narod.ru/aspekty4.htm

Продемонстрирую метод на примере построения пары ОЛК 7-го порядка. Первый латинский квадрат строится методом циклического сдвига, описанным в начале данной статьи, только в первой строке записывается не произвольная, а конкретная перестановка чисел. Эта перестановка для любого порядка n рассматриваемой группы порядков составляется так: в первой ячейке записывается 0, а дальше записываются числа от  n – 1 до 1 в убывающем порядке. Смотрите первый латинский квадрат на рис. 24. В этом примере циклический сдвиг выполняется с шагом 5. В общем случае для порядка n циклический сдвиг выполняется с шагом n – 2.

 

 

Рис. 24

 

Ортогональный соквадрат можно получить из этого латинского квадрата несколькими способами: отражением относительно горизонтальной (или вертикальной) оси симметрии, отражением относительно одной из главных диагоналей. Покажу ортогональный соквадрат, полученный отражением относительно главной диагонали, начинающейся с 0 (рис. 25).

 

 

Рис. 25

 

Ещё раз подчеркну: данный метод работает для любого нечётного порядка не кратного 3.

 

Наверное, существует ещё множество интересных схем построения латинских квадратов. Если вы знаете такие схемы, пишите мне.

 

 

15 апреля 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

 

       Пишите мне!

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

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