МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Восточно-Сибирский государственный университет технологий и управления»

(ФГБОУ ВПО ВСГУТУ)

Кафедра: «Стандартизация, метрология и управление качеством»

Реферат

по дисциплине: «Математический анализ планов эксперимента»

на тему: «Латинские квадраты»

Проверила: Доржиева А.А.

Выполнила: Гаськова А.С.

Улан-Удэ

2015 Г Содержание

1 Понятие латинского квадрата 3

2 История исследований латинских квадратов 3

3 Отношения эквивалентности на множестве латинских квадратов 6

4 Ортогональные латинские квадраты 7

5 Частичные квадраты 9

Список использованных источников 10

1 Понятие латинского квадрата

Латинский квадрат n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множестваM таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:

В настоящее время в качестве множества M обычно берётся множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлериспользовал буквылатинского алфавита, откуда латинские квадраты и получили своё название.[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэлиаддитивной группыкольца: lij= (i+j-1) mod n.

2 История исследований латинских квадратов

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты Жаком Озанамомв1725 году.[2]В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера[1]. Он занимался в ней методами построениямагических квадратови предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечётных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в каре так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания.

В 1890 годуКэливывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в1708 году).[3]

В 1900 годугипотеза Эйлера для n = 6 была подтверждена G. Tarry.[4]Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 годуMacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов.[5]В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 годуFisher предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.[6]

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами итаблицами Кэликвазигрупп существует взаимно-однозначное соответствие.

В 1959 годуBose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в1960 годуони же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.[7]

Число латинских квадратов[править|править вики-текст]

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) дает формула

[8]

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:

Число R(n) нормализованных латинских квадратов n-го порядка в n!(n-1)! раз меньше, чем L(n).

Точные значения величины L(n) известны для n от 1 до 11:[4]

Число латинских квадратов
n	R(n)	L(n)	Автор и год
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161280	Euler (1782)
6	9408	812851200	Frolov (1890)

Продолжение таблицы

7	16942080	61479419904000	Sade (1948)
8	535281401856	108776032459082956800	Wells (1967)
9	377597570964258816	5524751496156892842531225600	Bammel и Rothstein (1975)
10	7580721483160132811489280	9982437658213039871725064756920320000	McKay и Rogoyski (1995)
11	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000	McKay и Wanless (2005)