Взаимно ортогональные латинские квадраты

В комбинаторике два латинских квадрата одинакового размера ( порядка ) называются ортогональными , если при наложении упорядоченные парные записи в позициях все различны. Набор латинских квадратов, все одного порядка, все пары которых ортогональны, называется набором взаимно ортогональных латинских квадратов . Эта концепция ортогональности в комбинаторике тесно связана с концепцией блокировки в статистике , которая гарантирует, что независимые переменные действительно независимы без скрытых смешивающих корреляций. Таким образом, «ортогональный» является синонимом «независимого» в том смысле, что знание значения одной переменной не дает никакой дополнительной информации о вероятном значении другой переменной.

Более старый термин для пары ортогональных латинских квадратов — греко-латинский квадрат , введенный Эйлером.

Греко-латинские квадраты

Греко -латинский квадрат или квадрат Эйлера или пара ортогональных латинских квадратов порядка $n$ над двумя множествами $S$ и $T$ (которые могут быть одним и тем же), каждое из которых состоит из $n$ символов, представляет собой расположение ячеек $размером n \times n$ , каждая ячейка содержит упорядоченную пару $(s, t)$ , где $s$ принадлежит $S$ , а $t$ принадлежит $T$ , так что каждая строка и каждый столбец содержат каждый элемент $S$ и каждый элемент $T$ ровно один раз, и что никакие две ячейки не содержат одну и ту же упорядоченную пару.

Греко-латинские квадраты (пары ортогональных латинских квадратов)
Заказать 3
Заказать 4
Заказать 5

Расположение $s$ -координат само по себе (которые можно рассматривать как латинские символы) и $t$ -координат (греческие символы) образует латинский квадрат . Поэтому греко-латинский квадрат можно разложить на два ортогональных латинских квадрата. Ортогональность здесь означает, что каждая пара $(s, t)$ из декартова произведения $S \times T$ встречается ровно один раз.

Ортогональные латинские квадраты были подробно изучены Леонардом Эйлером , который взял два множества: $S = {A, B, C, ...$ }, первые $n$ заглавных букв латинского алфавита , и $T = {α, β, γ, ...$ }, первые $n$ строчных букв греческого алфавита — отсюда и название греко-латинский квадрат.

Существование

Когда греко-латинский квадрат рассматривается как пара ортогональных латинских квадратов, говорят, что каждый из латинских квадратов имеет ортогонального партнера . В произвольном латинском квадрате выбор позиций, по одной в каждой строке и по одной в каждом столбце, все элементы которых различны, называется трансверсалью этого квадрата. ^[1] Рассмотрим один символ в греко-латинском квадрате. Позиции, содержащие этот символ, должны быть все в разных строках и столбцах, и, кроме того, все другие символы в этих позициях должны быть различны. Следовательно, если рассматривать их как пару латинских квадратов, позиции, содержащие один символ в первом квадрате, соответствуют трансверсали во втором квадрате (и наоборот).

Данный латинский квадрат порядка n имеет ортогональное сопряжение тогда и только тогда, когда он имеет n непересекающихся трансверсалей. ^[2]

Таблица Кэли (без границ) любой группы нечетного порядка образует латинский квадрат, имеющий ортогональное сопряжение. ^[2]

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

Эйлеру удалось построить греко-латинские квадраты порядков, кратных четырем ^[2], и, по-видимому, он знал о следующем результате.

Никакие греко-латинские квадраты, основанные на группах, не могут существовать, если порядок является нечетным кратным двум (то есть равен 4k $+$ 2 для некоторого положительного целого числа $k$ ). ^[3]

История

Хотя ортогональные латинские квадраты были признаны за его оригинальную математическую трактовку предмета, они появились еще до Эйлера. В форме старой головоломки с игральными картами ^[4] построение набора 4 x 4 было опубликовано Жаком Озанамом в 1725 году. ^[5] Задача состояла в том, чтобы взять всех тузов, королей, дам и валетов из стандартной колоды карт и расположить их в сетке 4 x 4 таким образом, чтобы каждая строка и каждый столбец содержали все четыре масти, а также по одной карте каждого номинала. У этой задачи есть несколько решений.

Распространенным вариантом этой задачи было расположить 16 карт таким образом, чтобы, в дополнение к ограничениям по строкам и столбцам, каждая диагональ содержала все четыре номинала и все четыре масти.

По словам Мартина Гарднера , который представил этот вариант задачи в своей колонке «Математические игры» за ноябрь 1959 года , ^[6] число различных решений было неверно указано Рауз Болл как 72. Эта ошибка сохранялась в течение многих лет, пока правильное значение 144 не было найдено Кэтлин Оллереншоу . Каждое из 144 решений имеет восемь отражений и вращений, что дает в общей сложности 1152 решения. Решения 144×8 можно разделить на следующие два класса эквивалентности :

Для каждого из двух решений можно получить 24×24 = 576 решений, переставляя четыре масти и четыре номинала независимо. Никакая перестановка не преобразует два решения друг в друга, поскольку масти и номиналы различны.

Проблема тридцати шести офицеров

Задача, похожая на карточную задачу, описанную выше, была в ходу в Санкт-Петербурге в конце 1700-х годов, и, согласно фольклору, Екатерина Великая попросила Эйлера решить ее, поскольку он в то время находился при ее дворе. ^[7] Эта задача известна как задача о тридцати шести офицерах , ^[8] и Эйлер представил ее следующим образом: ^[9]^[10]

Очень любопытный вопрос, который некоторое время упражнял изобретательность многих людей, вовлек меня в следующие исследования, которые, кажется, открывают новую область анализа, в частности, изучение комбинаций. Вопрос вращается вокруг расстановки 36 офицеров, взятых из 6 разных полков, так, чтобы они были выстроены в квадрат так, чтобы в каждой линии (как горизонтальной, так и вертикальной) было 6 офицеров разных званий и разных полков.
— Леонард Эйлер

Перерисовка греко-латинского квадрата «Порядок-10» журнала Scientific American за ноябрь 1959 г. — в файле SVG наведите курсор на буквы, чтобы скрыть фон, и наоборот.

Эйлер не смог решить эту задачу, но в этой работе он продемонстрировал методы построения греко-латинских квадратов, где $n$ нечетно или кратно 4. Заметив, что не существует квадрата второго порядка, и будучи неспособным построить квадрат шестого порядка, он предположил, что не существует ни одного для любого нечетного четного числа $n \equiv 2 ( mod 4).$ Несуществование квадратов шестого порядка было подтверждено в 1901 году Гастоном Тарри с помощью доказательства исчерпанием . ^[11]^[12] Однако гипотеза Эйлера сопротивлялась решению до конца 1950-х годов, но проблема привела к важной работе в комбинаторике . ^[13]

В 1959 году Р. К. Бозе и С. С. Шрикханде построили несколько контрпримеров (названных спойлерами Эйлера ) порядка 22, используя математические идеи. ^[14] Затем Э. Т. Паркер нашел контрпример порядка 10, используя часовой компьютерный поиск на военном компьютере UNIVAC 1206, работая в подразделении UNIVAC компании Remington Rand (это была одна из самых ранних задач комбинаторики, решенных на цифровом компьютере ).

В апреле 1959 года Паркер, Бозе и Шрикханде представили свою статью, показывающую, что гипотеза Эйлера ложна для всех $n \geq 7.$ ^[15] Таким образом, греко-латинские квадраты существуют для всех порядков $n > 1,$ за исключением $n = 2, 6.$ В выпуске Scientific American за ноябрь 1959 года Мартин Гарднер опубликовал этот результат. ^[6] На обложке — опровержение гипотезы Эйлера размером 10 × 10.

Проблема тридцати шести запутанных офицеров

Расширения взаимно ортогональных латинских квадратов в квантовую область изучаются с 2017 года. ^[17] В этих конструкциях вместо уникальности символов элементы массива являются квантовыми состояниями, которые должны быть ортогональны друг другу в строках и столбцах. В 2021 году индийско-польская группа физиков (Ратер, Бурхардт, Брузда, Райхель-Миелдзёч, Лакшминараян и Жичковский ) нашла массив квантовых состояний, который дает пример взаимно ортогональных квантовых латинских квадратов размера 6; или, что эквивалентно, расположение 36 офицеров, которые запутаны. ^[16]^[18]^[19] Эта установка решает обобщение задачи 36 офицеров Эйлера, а также предоставляет новый квантовый код обнаружения ошибок , позволяющий кодировать 6-уровневую систему в три 6-уровневые системы, которые удостоверяют возникновение одной ошибки.

Примеры взаимно ортогональных латинских квадратов (MOLS)

Набор латинских квадратов одного порядка, такой, что каждая пара квадратов ортогональна (то есть образует греко-латинский квадрат), называется набором взаимно ортогональных латинских квадратов (или попарно ортогональных латинских квадратов ) и обычно сокращается до MOLS или MOLS( n ), когда порядок указан явно.

Например, набор MOLS(4) задается следующим образом: ^[20]

{\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\4&3&2&1\\2&1&4&3\\3&4&1&2\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\3&4&1&2\\4&3&2&1\\2&1&4&3\end{matrix}}.

И набор MOLS(5): ^[21]

{\begin{matrix}1&2&3&4&5\\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\3&4&5&1&2\\5&1&2&3&4\\2&3&4&5&1\\4&5&1&2&3\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix}}\qquad {\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}}.

Хотя можно представить MOLS в форме «составной» матрицы, подобной, например, греко-латинским квадратам,

Для примера MOLS(5) выше более типично компактное представление MOLS в виде ортогонального массива (см. ниже). ^[22]

В примерах MOLS, приведенных до сих пор, для каждого квадрата использовался один и тот же алфавит (набор символов), но это не обязательно, как показывают греко-латинские квадраты. Фактически, для каждого квадрата набора MOLS могут использоваться совершенно разные наборы символов. Например,

представляет собой представление приведенного выше примера составной системы MOLS(5), где четыре системы MOLS имеют следующие алфавиты:

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

Таким образом, приведенная выше таблица позволяет проверить пять значений в каждом из четырех различных измерений всего за 25 наблюдений вместо 625 (= 5 ⁴ ) наблюдений, требуемых в полном факторном дизайне . Поскольку пять слов охватывают все 26 букв алфавита между ними, таблица позволяет проверить каждую букву алфавита в пяти различных шрифтах и цветовых сочетаниях.

Число взаимно ортогональных латинских квадратов

Свойство взаимной ортогональности набора MOLS не зависит от

Переставляя строки всех квадратов одновременно,
Переставляем столбцы всех квадратов одновременно, и
Перестановка элементов в любом квадрате, независимо.

Используя эти операции, любой набор MOLS можно привести к стандартной форме , что означает, что первая строка каждого квадрата идентична и обычно располагается в некотором естественном порядке, а первый столбец одного квадрата также находится в этом порядке. ^[23] Примеры MOLS(4) и MOLS(5) в начале этого раздела приведены к стандартной форме.

Приведя набор MOLS( $n$ ) в стандартную форму и изучив записи во второй строке и первом столбце каждого квадрата, можно увидеть, что может существовать не более $n$ − 1 квадратов. ^[24] Набор из $n$ − 1 MOLS( $n$ ) называется полным набором MOLS . Известно, что полные наборы существуют, когда $n$ является простым числом или степенью простого числа (см. Конечная конструкция поля ниже). Однако число MOLS, которые могут существовать для данного порядка $n ,$ неизвестно для общего $n$ и является областью исследований в комбинаторике .

Проективные плоскости

Набор из $n$ − 1 MOLS( $n$ ) эквивалентен конечной аффинной плоскости порядка $n$ (см. Сети ниже). ^[10] Поскольку каждая конечная аффинная плоскость однозначно продолжается до конечной проективной плоскости того же порядка, эта эквивалентность может быть также выражена в терминах существования этих проективных плоскостей. ^[25]

Как упоминалось выше, полные наборы MOLS( $n$ ) существуют, если $n$ является простым числом или степенью простого числа, поэтому проективные плоскости таких порядков существуют. Конечные проективные плоскости с порядком, отличным от этих, и, следовательно, полные наборы MOLS таких порядков, как известно, не существуют. ^[10]

Единственным общим результатом о несуществовании конечных проективных плоскостей является теорема Брука–Райзера , которая гласит, что если проективная плоскость порядка $n$ существует и $n$ ≡ 1 (mod 4) или $n$ ≡ 2 (mod 4), то $n$ должно быть суммой двух (целых) квадратов. ^[26] Это исключает, например, проективные плоскости порядков 6 и 14, но не гарантирует существование плоскости, когда $n$ удовлетворяет условию. В частности, $n$ = 10 удовлетворяет условиям, но проективной плоскости порядка 10 не существует, как было показано очень долгим компьютерным поиском, ^[27] что, в свою очередь, подразумевает, что не существует девяти МОЛС порядка 10.

Никаких других результатов существования не известно. По состоянию на 2020 год ^{[обновлять]}наименьший порядок, для которого существование полного набора MOLS не определено, равен 12. ^[10]

Теорема Макниша

Известно, что минимальное число MOLS( $n$ ) равно 2 для всех $n,$ за исключением $n$ = 2 или 6, где оно равно 1. Однако можно сказать больше, а именно, ^[28]

Теорема Макниша : Если — разложение целого числа $n$ на степени различных простых чисел , то $n=p_{1}^{\альфа _{1}}p_{2}^{\альфа _{2}}\cdots p_{r}^{\альфа _{r}}$ $p_{1},p_{2},\cdots ,p_{r}$

минимальное число MOLS(

n

)

\geq {\underset {i}{\operatorname {min} }}\{p_{i}^{\alpha _{i}}-1\}.

Теорема Макниша не дает очень хорошей нижней границы, например, если $n$ ≡ 2 (mod 4), то есть в разложении на простые множители есть единственная 2, теорема дает нижнюю границу 1, которая оказывается ниже, если $n$ > 6. С другой стороны, она дает правильное значение, когда $n$ является степенью простого числа.

Для общих составных чисел число MOLS неизвестно. Первые несколько значений, начинающихся с $n$ = 2, 3, 4..., это 1, 2, 3, 4, 1, 6, 7, 8, ... (последовательность A001438 в OEIS ).

Наименьший случай, для которого точное число MOLS( $n$ ) неизвестно, это $n$ = 10. Из греко-латинской квадратной конструкции следует, что должно быть по крайней мере два, а из-за отсутствия проективной плоскости порядка 10 следует, что их меньше девяти. Однако ни один набор из трех MOLS(10) так и не был найден, хотя многие исследователи пытались обнаружить такой набор. ^[29]

Для достаточно большого $n$ число MOLS больше, чем , таким образом, для каждого $k$ существует только конечное число $n,$ такое, что число MOLS равно $k$ . ^[30] Более того, минимум равен 6 для всех $n$ > 90. ${\sqrt[{14.8}]{n}}$

Конструкция конечного поля

Полный набор MOLS( $q$ ) существует, когда $q$ является простым числом или степенью простого числа. Это следует из конструкции, которая основана на конечном поле GF ( $q$ ), которое существует только если $q$ является простым числом или степенью простого числа. ^[31] Мультипликативная группа GF ( $q$ ) является циклической группой и, таким образом, имеет генератор λ, что означает, что все ненулевые элементы поля могут быть выражены как различные степени λ. Назовите $q$ элементов GF ( $q$ ) следующим образом:

α ₀ = 0, α ₁ = 1, α ₂ = λ, α ₃ = λ ² , ..., α _{$q$ -1} = λ ^{$q$ -2} .

Теперь λ ^{$q$ -1} = 1 и правило произведения в терминах α имеет вид α _$i$ α _$j$ = α _$t$ , где $t$ = $i$ + $j$ -1 (mod $q$ -1). Латинские квадраты строятся следующим образом, ( $i, j$ )-й элемент в латинском квадрате L _$r$ (при $r$ ≠ 0) равен L _$r$ ( $i,j$ ) = α _$i$ + α _$r$ α _$j$ , где все операции происходят в GF ( $q$ ). В случае, если поле является простым полем ( $q$ = $p$ a simple), где элементы поля представлены обычным образом, как целые числа по модулю $p$ , соглашение об именовании выше можно опустить, и правило построения можно упростить до L _$r$ ( $i,j$ ) = $i$ + $rj$ , где $r$ ≠ 0 и $i$ , $j$ и $r$ являются элементами GF ( $p$ ), и все операции происходят в GF ( $p$ ). Приведенные выше примеры MOLS(4) и MOLS(5) возникли из этой конструкции, хотя и с изменением алфавита.

Не все полные наборы MOLS возникают из этой конструкции. Проективная плоскость, которая связана с полным набором MOLS, полученным из этой конструкции поля, является специальным типом, дезарговой проективной плоскостью . Существуют недезарговы проективные плоскости , и их соответствующие полные наборы MOLS не могут быть получены из конечных полей. ^[32]

Ортогональный массив

Ортогональный массив OA( $k,n$ ) мощности два и индекса один — это массив $A$ $размером n2 \times$ $k (k$ ≥ $2$ и $n$ ≥ 1, целые числа) с элементами из набора размера $n,$ таким образом, что в любых двух столбцах $A$ ( мощность ) каждая упорядоченная пара символов появляется ровно в одной строке $A$ ( индекс ). ^[33]

OA( $s$ + 2, $n$ ) эквивалентно $s$ MOLS( $n$ ). ^[33] Например, пример MOLS(4), приведенный выше и повторенный здесь,

{\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\&L_{1}&&\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\4&3&2&1\\2&1&4&3\ \3&4&1&2\\&L_{2}&&\end{matrix}}\qquad \qquad {\begin{matrix}1&2&3&4\\3&4&1&2\\4&3&2&1\\2&1&4&3\\&L_{3}&&\end{matrix}}

можно использовать для формирования OA(5,4):

где записи в столбцах, помеченных r и c, обозначают строку и столбец позиции в квадрате, а остальная часть строки для фиксированных значений r и c заполняется записью в этой позиции в каждом из латинских квадратов. Этот процесс обратим; учитывая OA( $s$ , $n$ ) с $s$ ≥ 3, выберите любые два столбца, которые будут играть роли r и c , а затем заполните латинские квадраты записями в оставшихся столбцах.

Более общие ортогональные массивы представляют собой обобщения концепции MOLS, такие как взаимно ортогональные латинские кубы.

Сетки

(Геометрическая) ( $k,n$ )-сеть — это множество из $n$ ² элементов, называемых точками , и множество из $kn$ подмножеств, называемых линиями или блоками, каждое из которых имеет размер $n,$ со свойством, что две различные линии пересекаются не более чем в одной точке. Более того, линии можно разбить на $k$ параллельных классов (никакие две из их линий не пересекаются), каждый из которых содержит $n$ линий. ^[34]

( $n$ + 1, $n$ )-сеть — это аффинная плоскость порядка $n$ .

Набор из $k$ MOLS( $n$ ) эквивалентен ( $k$ + 2, $n$ )-сети. ^[10]

Чтобы построить ( $k$ + 2, $n$ )-сеть из $k$ MOLS( $n$ ), представьте MOLS как ортогональный массив OA( $k$ + 2, $n$ ) (см. выше). Упорядоченные пары записей в каждой строке ортогонального массива в столбцах, обозначенных $r$ и $c$ , будут считаться координатами $n$ ² точек сети. Каждый другой столбец (то есть латинский квадрат) будет использоваться для определения линий в параллельном классе. $N$ линий, определенных столбцом, обозначенным L _i, будут обозначены l _ij . Точки на l _ij будут теми, координаты которых соответствуют строкам, где запись в столбце L _i равна $j$ . Существует два дополнительных параллельных класса, соответствующих столбцам $r$ и $c$ . Линии $r$ _j и $c$ _j состоят из точек, первые координаты которых равны $j$ , или вторые координаты равны $j$ соответственно. Это построение обратимо. ^[35]

Например, OA(5,4) в приведенном выше разделе может быть использован для построения (5,4)-сети (аффинной плоскости порядка 4). Точки на каждой линии задаются следующим образом (каждая строка ниже представляет собой параллельный класс линий):

Поперечные конструкции

Трансверсальная конструкция с $k$ группами размера $n$ и индексом λ, обозначаемая T[ $k$ , λ; $n$ ], представляет собой тройку ( $X, G, B$ ), где: ^[36]

$X$ — множество $kn$ многообразий;
$G = {G 1, G 2, ..., G k$ } — семейство $kn$ -множеств (называемых группами , но не в алгебраическом смысле), которые образуют разбиение $X$ ;
$B$ — это семейство $k$ -множеств (называемых блоками ) многообразий, такое, что каждое $k$ -множество в $B$ пересекает каждую группу $G i$ ровно в одном многообразии, и любая пара многообразий, принадлежащих разным группам, встречается вместе ровно в λ-блоках в $B$ .

Существование конструкции T[ $k$ ,1; $n$ ] эквивалентно существованию $k$ -2 MOLS( $n$ ). ^[37]

Трансверсальная конструкция T[ $k$ ,1; $n$ ] — это структура двойной инцидентности ( $k,n$ )-сети. То есть, она имеет $nk$ точек и $n2$ ^блоков . Каждая точка находится в $n$ блоках; каждый блок содержит $k$ точек. Точки попадают в $k$ классов эквивалентности (групп) размера $n,$ так что две точки в одной и той же группе не содержатся в блоке, в то время как две точки в разных группах принадлежат ровно одному блоку. ^[38]

Например, используя (5,4)-сеть из предыдущего раздела, мы можем построить трансверсальную схему T[5,1;4]. Блок, связанный с точкой ( $i, j$ ) сетки, будет обозначен $b$ _ij . Точки схемы будут получены из следующей схемы: $r$ _i ↔ $i$ , $c$ _j ↔ 5 $j$ , и $l$ _ij ↔ 5 $i$ + $j$ . Точки схемы, таким образом, обозначаются целыми числами 1, ..., 20. Блоки схемы следующие:

Пять «групп» таковы:

Теория графов

Набор из $k$ MOLS( $n$ ) эквивалентен рёберному разбиению полного ( $k$ + 2)-дольного графа K _{n ,..., n} на полные подграфы порядка $k$ + 2. ^[10]

Приложения

Взаимно ортогональные латинские квадраты имеют множество применений. Они используются в качестве отправной точки для построений в статистическом планировании экспериментов , составлении турниров , а также в кодах исправления и обнаружения ошибок . Интерес Эйлера к греко-латинским квадратам возник из его желания построить магические квадраты . Французский писатель Жорж Перек структурировал свой роман 1978 года «Жизнь: Руководство пользователя» вокруг греко-латинского квадрата 10×10.

Смотрите также

Примечания

^ В литературе это понятие известно под несколькими названиями: формула директрисы (Эйлера), директриса , 1-перестановка и диагональ среди прочих. (Dénes & Keedwell 1974, стр. 29)
^ abc Dénes & Keedwell 1974, с. 155
^ Денес и Кидуэлл 1974, с. 156
^ Кнут, Дональд (2011), Искусство программирования, т. 4A: Комбинаторные алгоритмы, часть 1, Addison-Wesley, стр. xv+883pp, ISBN 978-0-201-03804-0. Опечатки: [1]
^ Озанам, Жак (1725), Математический и физический отдых, том. IV, с. 434, решение на рис. 35
^ ab Gardner 1966, стр. 162-172
^ ван Линт и Уилсон 1993, стр.251
^ PA MacMahon (1902). «Магические квадраты и другие задачи на шахматной доске». Труды Королевского института Великобритании . XVII : 50–63.
^ Эйлер: Recherches sur une nouvelle espece de quarres magiques, написанное в 1779 году, опубликованное в 1782 году.
^ abcdef Colbourn & Dinitz 2007, стр. 162
^ Тарри, Гастон (1900). «Проблема 36 офицеров». Compte Rendu de l'Association Française pour l'Avancement des Sciences . 1 . Секретариат Ассоциации: 122–123.
^ Тарри, Гастон (1901). «Проблема 36 офицеров». Compte Rendu de l'Association Française pour l'Avancement des Sciences . 2 . Секретариат Ассоциации: 170–203.
^ ван Линт и Уилсон 1993, стр.267
^ Бозе, Р. К.; Шрикханде, С. С. (1959), «О ложности гипотезы Эйлера о несуществовании двух ортогональных латинских квадратов порядка 4t + 2», Труды Национальной академии наук США , 45 (5): 734–737, Bibcode : 1959PNAS...45..734B, doi : 10.1073/pnas.45.5.734 , PMC 222625 , PMID 16590435
^ Бозе, Р. К.; Шрикханде, С. С.; Паркер, Э. Т. (1960), «Дальнейшие результаты построения взаимно ортогональных латинских квадратов и ложность гипотезы Эйлера», Канадский математический журнал , 12 : 189–203, doi : 10.4153/CJM-1960-016-5 , MR 0122729
^ ab Rather, Suhail Ahmad; Burchardt, Adam; Bruzda, Wojciech; Rajchel-Mieldzioć, Grzegorz; Lakshminarayan, Arul; Życzkowski, Karol (2022), "Тридцать шесть запутанных офицеров Эйлера: квантовое решение классически невозможной проблемы", Physical Review Letters , 128 (8): 080507, arXiv : 2104.05122 , Bibcode : 2022PhRvL.128h0507R, doi : 10.1103/PhysRevLett.128.080507, PMID 35275648, S2CID 236950798
^ Гойенече, Дардо; Раисси, Захра; Ди Мартино, Сара; Жичковски, Кароль (2018), «Запутывание и квантовые комбинаторные модели», Physical Review A , 97 (6): 062326, arXiv : 1708.05946 , Bibcode : 2018PhRvA..97f2326G, doi :10.1103/PhysRevA.97.062326, S2CID 51532085
^ Гаристо, Дэн (2022), «243-летняя «невозможная» головоломка Эйлера получает квантовое решение», Quanta Magazine
^ Паппас, Стефани (2022), «Многовековая «невозможная» математическая задача решена с помощью странной физики кота Шредингера», LiveScience
^ Колборн и Диниц 2007, с. 160
^ Колборн и Диниц 2007, с. 163
^ Маккей, Мейнерт и Мирволд 2007, стр. 98
^ Денес и Кидуэлл 1974, с. 159
^ Денес и Кидуэлл 1974, с. 158
^ Термин «порядок», используемый здесь для MOLS, аффинных плоскостей и проективных плоскостей, определяется по-разному в каждой настройке, но эти определения согласованы таким образом, что численное значение одинаково.
^ Брук, Р. Х.; Райзер, Х. Дж. (1949), «Несуществование некоторых конечных проективных плоскостей», Канадский журнал математики , 1 : 88–93, doi : 10.4153/cjm-1949-009-2 , S2CID 123440808
^ Лэм, CWH (1991), «Поиск конечной проективной плоскости порядка 10», American Mathematical Monthly , 98 (4): 305–318, doi :10.2307/2323798, JSTOR 2323798
^ Денес и Кидуэлл 1974, с. 390
^ Маккей, Мейнерт и Мирволд 2007, стр. 102
^ Lenz, H.; Jungnickel, D.; Beth, Thomas (ноябрь 1999 г.). Теория дизайна Томаса Бета. Cambridge Core. doi :10.1017/cbo9781139507660. ISBN 9780521772310. Получено 2019-07-06 .
^ Денес и Кидуэлл 1974, с. 167
^ Денес и Кидуэлл 1974, с. 169
^ ab Stinson 2004, стр. 140
^ Колборн и Диниц 2007, с. 161
^ Денес и Кидуэлл 1974, с. 270
^ Улица и улица 1987, стр. 133
^ Улица и улица 1987, стр. 135
^ ван Линт и Уилсон 1993, стр.257

Ссылки

Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник комбинаторных конструкций (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 978-1-58488-506-1
Денес, Дж.; Кидвелл, А.Д. (1974), Латинские квадраты и их приложения , Нью-Йорк-Лондон: Academic Press, стр. 547, ISBN 0-12-209350-X, МР 0351850
Гарднер, Мартин (1966), Новые математические размышления Мартина Гарднера из Scientific American , Fireside, ISBN 0-671-20913-2
Маккей, Брендан Д.; Мейнерт, Элисон; Мирволд, Венди (2007), «Маленькие латинские квадраты, квазигруппы и петли» (PDF) , Журнал комбинаторных конструкций , 15 (2): 98–119, doi :10.1002/jcd.20105, S2CID 82321|doi-broken-date=2020-10-03| збл=1112.05018 | citeseerx=10.1.1.151.3043}}
Рагхаварао, Дамараджу (1988), Конструкции и комбинаторные проблемы в планировании экспериментов (исправленное переиздание издания Wiley 1971 г.), Нью-Йорк: Довер
Рагхаварао, Дамараджу и Паджетт, Л. В. (2005). Блочные конструкции: анализ, комбинаторика и приложения . World Scientific.
Стинсон, Дуглас Р. (2004), Комбинаторные конструкции / Конструкции и анализ , Springer, ISBN 978-0-387-95487-5
Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987), Комбинаторика экспериментального проектирования , Oxford UP [Clarendon], ISBN 0-19-853256-3
ван Линт, Дж. Х.; Уилсон, Р. М. (1993), Курс комбинаторики , Cambridge University Press, ISBN 978-0-521-42260-4

Внешние ссылки

Головоломка Леонарда Эйлера о 36 офицерах Архив избранных колонок AMS (Латинские квадраты на практике и в теории II)
Вайсштейн, Эрик В. «Проблема 36 офицеров». Математический мир .
Работа Эйлера о латинских квадратах и квадратах Эйлера в конвергенции
Java-инструмент, который помогает строить греко-латинские квадраты (он не строит их сам) на этапе cut-the-knot
Все, кроме квадрата: от магических квадратов до судоку
Исторические факты и взаимосвязь с магическими квадратами, приложение Javascript для решения греко-латинских квадратов размером от 1x1 до 10x10 и соответствующий исходный код (Javascript в браузере Firefox и мобильных устройствах HTML5)
Грайм, Джеймс. "Квадраты Эйлера" (видео) . YouTube . Брэди Харан . Архивировано из оригинала 2021-12-12 . Получено 9 мая 2020 .