Латинский квадрат | это... Что такое Латинский квадрат? (original) (raw)
Лати́нский квадра́т _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.
Содержание
- 1 История исследований латинских квадратов
- 2 Число латинских квадратов
- 3 Отношения эквивалентности на множестве латинских квадратов
- 4 Ортогональные латинские квадраты
- 5 Частичные квадраты
- 6 Нерешенные задачи
- 7 Применение
- 8 Игры и головоломки с латинскими квадратами
- 9 См. также
- 10 Примечания
- 11 Литература
История исследований латинских квадратов
Окно в честь Фишера с латинским квадратом 7-го порядка. Кембридж
Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.
Пары ортогональных латинских квадратов впервые были упомянуты J. Ozanam в 1725 году.[2] В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:
Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.
Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).
Важной вехой в истории исследований латинских квадратов стала работа Эйлера.[1] Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечетных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4_t_+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) дает формула
Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком на множестве M. Пример нормализованного латинского квадрата:
Число R(n) нормализованных латинских квадратов _n_-го порядка в n!(n-1)! раз меньше, чем L(n).
Точные значения величины L(n) известны для n от 1 до 11:[9]
Число латинских квадратов
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) |
Отношения эквивалентности на множестве латинских квадратов
Два латинских квадрата называют изотопными, если один из них может быть получен из другого в результате изотопии – композиции из перестановки строк, перестановки столбцов и замены элементов множества M по подстановке из симметрической группы S(M).
Изотопия является отношением эквивалентности, поэтому множество латинских квадратов _n_-го порядка разбивается на непересекающиеся изотопические классы. Из одного латинского квадрата можно получить с помощью изотопии (n!)3 эквивалентных, но некоторые из них при этом могут совпасть с исходным, это называется автопаратопией. Доля латинских квадратов с нетривиальной группой автопаратопий стремится к нулю с ростом n.[9]
Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.
Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.[10]
Число классов эквивалентности
n | Число главных классов | Число изотопических классов |
---|---|---|
1 | 1 | 1 |
2 | 1 | 1 |
3 | 1 | 1 |
4 | 2 | 2 |
5 | 2 | 2 |
6 | 12 | 22 |
7 | 147 | 564 |
8 | 283657 | 1676267 |
9 | 19270853541 | 115618721533 |
10 | 34817397894749939 | 208904371354363006 |
11 | 2036029552582883134196099 | 12216177315369229261482540 |
Ортогональные латинские квадраты
Два латинских квадрата L=(lij) и K=(kij) _n_-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:
Эйлер называл такие квадраты "полными". В его честь в научной литературе их раньше называли "эйлеровыми" или "греко-латинскими" (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).
Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.
Латинский квадрат L _n_-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.
Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов _n_-го порядка. Максимально возможная мощность N(n) такого множества равна _n_-1, в этом случае множество называется полным.
При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.
Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида fa(x,y)=ax+y при ненулевом a над полем .[11] Пример построения полного множества попарно ортогональных латинских квадратов 4-ого порядка (d – корень примитивного многочлена x2+x+1 над ):
Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.
Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):
Нижние оценки числа N(n)
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
N(n)≥ | 2 | 3 | 4 | 6 | 7 | 8 | 2 | 10 | 5 | 12 | 3 | 4 | 15 | 16 | 3 | 18 | 4 | 5 | 3 | 22 | 6 | 24 | 4 | 26 | 5 | 28 | 4 | 30 | 31 |
Построение ортогональных квадратов – сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.[12]
Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.
Частичные квадраты
Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.
Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной.
Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причем никакое его подмножество условию однозначности не удовлетворяет.[13] Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:
Мощность критического множества
n | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
С(n) | 0 | 1 | 3 | 7 | 11 | 18 |
Нерешенные задачи
Помимо задачи нахождения формулы для величины L(n), имеется большое количество нерешенных задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops'03:
- Оценка максимального числа трансверсалей в латинском квадрате _n_-го порядка
- Характеризация латинских подквадратов в таблице умножения луп Муфанг
- Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна
- Вычисление максимального t(n), при котором 2_t(n)_ делит величину L(n)
Применение
Пример использования латинского квадрата в филателии
Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.
Игры и головоломки с латинскими квадратами
Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов являются латинскими квадратами 3-го порядка.
Пользуются популярностью также задачи построения латинских квадратов и на их основе магических квадратов, обладающих дополнительными свойствами (например, диагональные квадраты).
См. также
Примечания
- ↑ 1 2 Euler L. Recherches sur une nouvelle espèce de quarrés magiques. — Middelburg, 1782.
- ↑ Ozanam J. Récréations mathématiques et physiques. — Paris, 1725.
- ↑ Cayley A. On Latin Squares // Messenger of mathematics. — 1890. — Т. XIX. — С. 135–137.
- ↑ Tarry G. Le problème des 36 officiers // Comptes Rendus Assoc. France Av. Sci.. — 1900. — Т. 29, part 2. — С. 170–203.
- ↑ MacNeish, Harris F. Euler Squares // Annals of Mathematics. — 1922. — Т. 23. — С. 221–227.
- ↑ Fisher R. A. Statistical methods for research workers. — Edinburg, London: Oliver & Boyd, 1925.
- ↑ Bose R. C.; Shrikhande S. S. On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2 // Proc. Nat. Acad. Sci. U.S.A.. — 1959. — Т. 45. — С. 734–737.
- ↑ van Lint J. H., Wilson R. M. A Course in Combinatorics. — Cambridge University Press, 1992.
- ↑ 1 2 McKay B. D., Wanless I. M. On the number of Latin Squares // Ann. Combin.. — 2005. — Т. 9. — С. 335-344.
- ↑ Черемушкин А. В. Почти все латинские квадраты имеют тривиальную группу автострофий // Прикладная дискретная математика. — 2009. — Т. 3(5). — С. 29–32.
- ↑ Bose R.S. On the applications of the properties of Galois fields to the problems of construction of Hyper-Graeco-Latin squares // Indian J. Stat.. — 1938. — Т. № 3. Part. 4. — С. 323–338.
- ↑ Dulmage A. L., Johnson D., Mendelsohn N. S. Orthomorphisms of groups and orthogonal Latin squares I // Canad. J. Math.. — 1961. — Т. 13. — С. 356–372.
- ↑ Nelder J. Critical sets in latin squares // CSIRO Division of Math. and Stats. — 1977. — Т. Newsletter, 38.
Литература
- Холл М. Комбинаторика, пер. с англ. М. 1970.
- Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest. 1974.
- Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.
- Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.
- Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York. 1998.
- Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010. Вып. 4(4). С. 95-104.
- Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2. С. 226—227.