Изображение на весь экран - нажать клавишу F11
 
ЛАТИНСКИЕ  КВАДРАТЫ  И  АРИФМЕТИКА СРАВНЕНИЙ

Цель.  Познакомиться с понятием латинского квадрата и применить теорию сравнений для построения алгоритмов их построения.

Лати́нский квадра́т – таблица  n × n,  заполненная  n  различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все  n  символов (каждый по одному разу).

Название "латинский квадрат" берёт начало от Леонарда Эйлера (Leonhard Euler), который использовал латинские буквы вместо цифр в таблице.
 

 

 

 
"Меланхолия"
Melencolia, 1514
Альбрехт Дюрер
Albrecht Dürer
 

Замечание.  Прежде латинского квадрата появился магический квадрат (изображённый на картине Альбрехта Дюрера "Меланхолия"), который определяется так.

Маги́ческий, или волше́бный квадра́т – это квадратная таблица, заполненная  n2  числами, таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях оказывается одинаковой.
 

В теме "Сравнения" были приведены примеры таблиц умножения и сложения в арифметике сравнений. Видно, что первая из них даёт латинский квадрат  55,  а вторая – латинский квадрат  44  (если отбросить нулевые строку и столбец).

 Таким образом, первая таблица задаёт латинский квадрат  mm  формулой  f(n;k) = n+k  mod m,  где  n  и  k  меняются от  0  до  m-1  и обозначают номера строк и столбцов соответственно (нумерация начинается с нуля).

 

+

0

1

2

3

4

 

 

0

1

2

3

4

0

0

1

2

3

4

 

 

0

0

0

0

0

0

1

1

2

3

4

0

 

 

1

0

1

2

3

4

2

2

3

4

0

1

 

 

2

0

2

4

1

3

3

3

4

0

1

2

 

 

3

0

3

1

4

2

4

4

0

1

2

3

 

 

4

0

4

3

2

1

Вторая таблица задаёт латинский квадрат  (p-1)(p-1)  формулой  f(n;k) = nk  mod p,  где  n  и  k  меняются от  1  до  p-1  и обозначают номера строк и столбцов соответственно (нумерация начинается с единицы), а  p – простое число.

Используя арифметику сравнений, можно построить новые латинские квадраты и написать алгоритмы их построения (формулы), которые можно впоследствии запрограммировать и превратить в демонстрационные программы.

Задания.

1) Исследовать формулу для построения латинских квадратов вида  mm  формулой  f(n;k) = n+k+c  mod m,  где  n  и  k  меняются от  0  до  m-1  и обозначают номера строк и столбцов соответственно (нумерация начинается с нуля), а  c – параметр, который можно менять от 0  до  m-1. Построить все латинские квадраты размера 44,  задаваемые этой формулой.

2) Исследовать формулу для построения латинских квадратов вида  (p-1)(p-1)  формулой  f(n;k) = cnk  mod p,  где  n  и  k  меняются от  1  до  p-1  и обозначают номера строк и столбцов соответственно (нумерация начинается с единицы),  p – простое число, а  c – параметр, который можно менять от 1  до  p-1. Построить все латинские квадраты размера  44,  задаваемые этой формулой.

3) При перестановке столбцов или строк латинского квадрата получается снова латинский квадрат.
Сколькими способами можно переставить столбцы и строки латинского квадрата  44?
Сколько различных латинских квадратов при этом получится?

4)* Заметим, что формулы  n+c1  mod m  и  k+c2  mod m  задают перестановки строк и столбцов, если  n  и  k  меняются от  0  до  m-1  и обозначают номера строк и столбцов соответственно,  c1  и  c2  – параметры, которые и определяют некоторые перестановки (параметры можно менять от 0  до  m-1).
Постройте все перестановки столбцов и строк, задаваемых этими формулами и найдите соответствующие этим перестановкам латинские квадраты.
Сколько их получилось? Сколько из них различных?
Напишите формулы этих квадратов, выразив их через  c1  и  c2  и дайте обоснование количеству различных латинских квадратов, получаемых такими перестановками.

5)* Заметим, что формулы  nc1  mod p  и  nc2  mod p  задают перестановки строк и столбцов, если  n  и  k  меняются от  1  до  p-1  и обозначают номера строк и столбцов соответственно,  p – простое число, а  c1  и  c2  – параметры, которые и определяют некоторые перестановки (параметры можно менять от 1  до  p-1).
Постройте все перестановки столбцов и строк, задаваемых этими формулами и найдите соответствующие этим перестановкам латинские квадраты.
Сколько их получилось? Сколько из них различных?
Напишите формулы этих квадратов, выразив их через  c1  и  c2  и дайте обоснование количеству различных латинских квадратов, получаемых такими перестановками.

 

Задание на межпредметные связи с информатикой.

Используя написанные выше формулы, написать Java-скрипт, генерирующий латинские квадраты.
Для знакомства с языком JavaScript читайте учебник автора известного самоучителя по этому языку Дмитриевой Марии Валерьевны, расположенный в свободном доступе на сайте кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета.

Работы учеников.
<< назад               вперед >>
В оглавление / В расписание уроков