Н. Макарова
ЕЩЁ ДВА МЕТОДА ПОСТРОЕНИЯ ЛАТИНСКИХ КВАДРАТОВ
Методы построения латинских квадратов описаны в статье http://www.natalimak1.narod.ru/metod2.htm
Здесь будут рассмотрены ещё два метода, найденные в книге “Старинные занимательные задачи” (С. Н. Олехник, Ю. В. Нестеренко, М. К. Потапов. – М.: Наука, Главная редакция физико-математической литературы, 1988).
Первый метод позволяет построить латинский квадрат любого порядка n = p – 1, где p – простое число (p ≥ 3).
Метод очень простой: каждый элемент aij латинского квадрата равен остатку от деления i*j на число p.
Покажу примеры, начиная с минимального порядка n = 2 (p = 3). Готовый латинский квадрат 2-го порядка вы видите на рис. 1.
|
1 |
2 |
|
2 |
1 |
Рис. 1
На рис. 2 показан латинский квадрат 4-го порядка (p = 5).
|
1 |
2 |
3 |
4 |
|
2 |
4 |
1 |
3 |
|
3 |
1 |
4 |
2 |
|
4 |
3 |
2 |
1 |
Рис. 2
Очень оригинальные получаются квадраты, элементы, расположенные симметрично относительно центра квадрата, равны. Этим свойством обладают все латинские квадраты, построенные данным методом. Латинские квадраты получаются нормализованные, при этом тождественная перестановка чисел находится не только в первой строке, но и в первом столбце.
Покажу ещё несколько латинских квадратов, на рис. 3 изображён латинский квадрат 6-го порядка (p = 7), на рис. 4 – латинский квадрат 10-го порядка (p = 11), на рис. 5 – латинский квадрат 12-го порядка (p = 13).
|
1 |
2 |
3 |
4 |
5 |
6 |
|
2 |
4 |
6 |
1 |
3 |
5 |
|
3 |
6 |
2 |
5 |
1 |
4 |
|
4 |
1 |
5 |
2 |
6 |
3 |
|
5 |
3 |
1 |
6 |
4 |
2 |
|
6 |
5 |
4 |
3 |
2 |
1 |
Рис. 3
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2 |
4 |
6 |
8 |
10 |
1 |
3 |
5 |
7 |
9 |
|
3 |
6 |
9 |
1 |
4 |
7 |
10 |
2 |
5 |
8 |
|
4 |
8 |
1 |
5 |
9 |
2 |
6 |
10 |
3 |
7 |
|
5 |
10 |
4 |
9 |
3 |
8 |
2 |
7 |
1 |
6 |
|
6 |
1 |
7 |
2 |
8 |
3 |
9 |
4 |
10 |
5 |
|
7 |
3 |
10 |
6 |
2 |
9 |
5 |
1 |
8 |
4 |
|
8 |
5 |
2 |
10 |
7 |
4 |
1 |
9 |
6 |
3 |
|
9 |
7 |
5 |
3 |
1 |
10 |
8 |
6 |
4 |
2 |
|
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Рис. 4
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
2 |
4 |
6 |
8 |
10 |
12 |
1 |
3 |
5 |
7 |
9 |
11 |
|
3 |
6 |
9 |
12 |
2 |
5 |
8 |
11 |
1 |
4 |
7 |
10 |
|
4 |
8 |
12 |
3 |
7 |
11 |
2 |
6 |
10 |
1 |
5 |
9 |
|
5 |
10 |
2 |
7 |
12 |
4 |
9 |
1 |
6 |
11 |
3 |
8 |
|
6 |
12 |
5 |
11 |
4 |
10 |
3 |
9 |
2 |
8 |
1 |
7 |
|
7 |
1 |
8 |
2 |
9 |
3 |
10 |
4 |
11 |
5 |
12 |
6 |
|
8 |
3 |
11 |
6 |
1 |
9 |
4 |
12 |
7 |
2 |
10 |
5 |
|
9 |
5 |
1 |
10 |
6 |
2 |
11 |
7 |
3 |
12 |
8 |
4 |
|
10 |
7 |
4 |
1 |
11 |
8 |
5 |
2 |
12 |
9 |
6 |
3 |
|
11 |
9 |
7 |
5 |
3 |
1 |
12 |
10 |
8 |
6 |
4 |
2 |
|
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Рис. 5
Примечание: здесь латинские квадраты строятся в нетрадиционной форме, то есть заполняются числами от 1 до n.
Поскольку все простые числа, начиная с 3, нечётные, данный метод применим только для построения латинских квадратов чётных порядков (разумеется, не всех чётных порядков, а только таких, что n = p – 1, где p – простое число).
Латинские квадраты, построенные данным методом, обладают ещё одним интересным свойством: сумма любых двух чисел, симметрично расположенных относительно горизонтальной (или вертикальной) оси симметрии квадрата, равна n + 1.
Латинский квадрат 12-го порядка обладает ещё одним свойством: хотя он не является диагональным, но суммы чисел в диагоналях равны суммам чисел в строках и в столбцах квадрата, то есть он является нетрадиционным магическим квадратом с магической константой 78. Таким свойством обладает также латинский квадрат 4-го порядка, построенный данным методом (см. рис. 2).
Метод настолько прост, что реализация его заняла у меня 5 минут. Вот программа, которая построит латинский квадрат любого порядка n = p – 1, если вы введёте в программу любое простое число p ≥ 3.
|
Программа построения латинских квадратов (язык QBASIC)
|
|
10 PRINT "VVEDITE PROSTOE CHISLO P" 15 INPUT P 20 N = P - 1 25 DIM A(N, N) 27 OPEN "MK.txt" FOR OUTPUT AS #1 30 FOR I = 1 TO N 35 FOR J = 1 TO N 40 K = I * J / P 45 A(I, J) = I * J - INT(K) * P 50 NEXT J 55 NEXT I 60 FOR X = 1 TO N 65 FOR Y = 1 TO N 70 PRINT A(X, Y); 75 PRINT #1, A(X, Y); 80 NEXT Y 85 PRINT : PRINT #1, 90 NEXT X 95 CLOSE #1 100 END
|
|
Составила Макарова Н. В. |
На рис. 6 показан латинский квадрат 16-го порядка (p = 17), построенный по приведённой программе.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
2 |
4 |
6 |
8 |
10 |
12 |
14 |
16 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
|
3 |
6 |
9 |
12 |
15 |
1 |
4 |
7 |
10 |
13 |
16 |
2 |
5 |
8 |
11 |
14 |
|
4 |
8 |
12 |
16 |
3 |
7 |
11 |
15 |
2 |
6 |
10 |
14 |
1 |
5 |
9 |
13 |
|
5 |
10 |
15 |
3 |
8 |
13 |
1 |
6 |
11 |
16 |
4 |
9 |
14 |
2 |
7 |
12 |
|
6 |
12 |
1 |
7 |
13 |
2 |
8 |
14 |
3 |
9 |
15 |
4 |
10 |
16 |
5 |
11 |
|
7 |
14 |
4 |
11 |
1 |
8 |
15 |
5 |
12 |
2 |
9 |
16 |
6 |
13 |
3 |
10 |
|
8 |
16 |
7 |
15 |
6 |
14 |
5 |
13 |
4 |
12 |
3 |
11 |
2 |
10 |
1 |
9 |
|
9 |
1 |
10 |
2 |
11 |
3 |
12 |
4 |
13 |
5 |
14 |
6 |
15 |
7 |
16 |
8 |
|
10 |
3 |
13 |
6 |
16 |
9 |
2 |
12 |
5 |
15 |
8 |
1 |
11 |
4 |
14 |
7 |
|
11 |
5 |
16 |
10 |
4 |
15 |
9 |
3 |
14 |
8 |
2 |
13 |
7 |
1 |
12 |
6 |
|
12 |
7 |
2 |
14 |
9 |
4 |
16 |
11 |
6 |
1 |
13 |
8 |
3 |
15 |
10 |
5 |
|
13 |
9 |
5 |
1 |
14 |
10 |
6 |
2 |
15 |
11 |
7 |
3 |
16 |
12 |
8 |
4 |
|
14 |
11 |
8 |
5 |
2 |
16 |
13 |
10 |
7 |
4 |
1 |
15 |
12 |
9 |
6 |
3 |
|
15 |
13 |
11 |
9 |
7 |
5 |
3 |
1 |
16 |
14 |
12 |
10 |
8 |
6 |
4 |
2 |
|
16 |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Рис. 6
Этот латинский квадрат также является нетрадиционным магическим квадратом с магической константой 136.
Приведу простые числа в первой сотне чисел, чтобы читатели знали, для каких порядков можно применить описанный метод. Простое число 2 пропускаю.
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Надеюсь, что читатели смогут продолжить ряд простых чисел.
Второй метод из указанной книги применим для построения латинского квадрата любого порядка. Он состоит в следующем: “Пусть n - произвольное целое положительное число и k – целое число, не имеющее общих с n делителей, больших единицы. Поместим на пересечении строки с номером a и столбца с номером b остаток от деления на n числа ak + b. Если остаток равен 0, то в соответствующую клетку поместим число n”. К цитате из книги следует добавить, что k тоже положительное число, и порядки квадратов представляют интерес при n ≥ 3.
Проиллюстрирую описанный метод примером построения латинского квадрата 9-го порядка (n = 9). Положим k = 4. На рис. 7 вы видите готовый латинский квадрат 9-го порядка.
|
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
|
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
|
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
|
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
|
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Рис. 7
Внимательно посмотрев на этот пример, легко увидеть, что данный метод представляет собой циклический сдвиг с постоянным шагом. Применение циклического сдвига было описано в указанной выше статье. Покажу ещё один пример тоже для латинского квадрата порядка 9, но с другим значением k, например, k = 2. На рис. 8 вы видите готовый латинский квадрат.
|
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
|
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
|
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
|
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
|
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
|
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
|
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Рис. 8
Легко увидеть, что этот латинский квадрат получается из квадрата с рис. 7 перестановкой строк.
Понятно, что для латинского квадрата 9-го порядка k может принимать значения: 1, 2, 4, 5, 7, 8.
В заключение ещё один пример: n = 10, k = 3. Смотрите готовый латинский квадрат на рис. 9.
|
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
3 |
|
7 |
8 |
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
|
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
|
6 |
7 |
8 |
9 |
10 |
1 |
2 |
3 |
4 |
5 |
|
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
|
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
3 |
4 |
|
8 |
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Рис. 9
Для латинского квадрата 10-го порядка k может принимать значения: 1, 3, 7, 9.
Из приведённых примеров легко увидеть, что k определяет шаг циклического сдвига.
Заметим интересную закономерность: в последней строке каждого латинского квадрата находится тождественная перестановка чисел. Если квадраты отразить относительно горизонтальной оси симметрии, они будут нормализованными.
В книге приведено строгое доказательство данного метода (стр. 101). Метод очень хорош тем, что позволяет построить латинский квадрат любого порядка, причём не один, хотя все квадраты одного порядка, построенные данным методом, изоморфны.
***
В книге рассматривается ещё вопрос о количестве латинских квадратов заданного порядка. Для порядков 3 и 4 дано подробное решение этого вопроса. Приведу его здесь. С точностью до перестановки строк и/или столбцов латинский квадрат 3-го порядка всего один, вы видите его на рис. 10.
|
1 |
2 |
3 |
|
2 |
3 |
1 |
|
3 |
1 |
2 |
Рис. 10
Далее в книге написано, что в этом латинском квадрате можно переставить столбцы 6 способами, а при каждом фиксированном положении столбцов перестановка второй и третьей строк даёт ещё два варианта. Таким образом, общее количество латинских квадратов 3-го порядка равно 12. Если считать латинские квадраты, получающиеся друг из друга перестановкой строк и/или столбцов, изоморфными, то все латинские квадраты, получающиеся из квадрата с рис. 10, будут изоморфны.
Теперь рассмотрим латинские квадраты 4-го порядка. С точностью до перестановок строк и/или столбцов латинских квадратов 4-го порядка четыре. Иными словами: есть только четыре неизоморфных латинских квадрата 4-го порядка (изоморфизм понимается в указанном выше смысле). Вы видите эти квадраты на рис. 11.
|
1 |
2 |
3 |
4 |
|
1 |
2 |
3 |
4 |
|
1 |
2 |
3 |
4 |
|
1 |
2 |
3 |
4 |
|
2 |
3 |
4 |
1 |
2 |
4 |
1 |
3 |
2 |
1 |
4 |
3 |
2 |
1 |
4 |
3 |
|||
|
3 |
4 |
1 |
2 |
3 |
1 |
4 |
2 |
3 |
4 |
1 |
2 |
3 |
4 |
2 |
1 |
|||
|
4 |
1 |
2 |
3 |
4 |
3 |
2 |
1 |
4 |
3 |
2 |
1 |
4 |
3 |
1 |
2 |
Рис. 11
В каждом из этих квадратов можно переставить столбцы 24 способами, а при каждом фиксированном положении столбцов перестановка второй, третьей и четвёртой строк даст ещё 6 вариантов. Таким образом, каждый неизоморфный квадрат порождает группу из 144 латинских квадратов, а всего латинских квадратов 4-го порядка будет 4 * 144 = 576.
Читатели могут аналогично посчитать количество латинских квадратов следующих порядков. Отмечу, что установлена нижняя граница количества латинских квадратов порядка n. Эта граница выражается формулой:
q(n) = n! * (n – 1)! * (n – 2)! … 3! * 2!
Для любого порядка n существует не менее q(n) латинских квадратов. Латинский квадрат 1-го порядка всего один. Латинских квадратов 2-го порядка два (один из них вы видите на рис. 1, второй получается перестановкой столбцов или строк). С ростом порядка количество латинских квадратов стремительно растёт. Для порядка 3 нижняя граница совпадает с фактическим количеством латинских квадратов. Для порядка 4 нижняя граница q(4) = 288, фактическое количество латинских квадратов 4-го порядка равно 576.
Нижняя граница для латинских квадратов 5-го порядка q(5) = 34560.
27 мая 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
Пишите мне!
На главную страницу
