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

История математики заполнена прозорливыми догадками — интуитивными гипотезами людей с большой математической интуицией. Часто эти гипотезы в течение столетий ждут своего доказательства или опровержения. Когда же, в конце концов, они появляются, то становятся математическими событиями первой величины. Об одном таком событии докладывалось в апреле 1959 года на ежегодной встрече Американского математического общества. Это опровержение известной гипотезы великого математика Леонарда Эйлера.

Леонард Эйлер (1707–1783)

Эйлер был убежден, что греко-латинские квадраты определенных порядков теоретически не существуют. Три математика — Е.Т. Паркер, Р.С. Боуз и С.С. Шрикханде — полностью опровергли гипотезу Эйлера. Они разработали методы построения нескольких квадратов, существование которых, по мнению последователей Эйлера, 177 лет считалось невозможным.

Но с подробностями следует повременить, познакомимся сперва с основным предметом этой статьи. Итак, знакомьтесь... 

Дадим определение:

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

Рисунок 1. Примеры латинских квадратов 2-го и 3-го порядков 

Известно, что латинские квадраты существуют для любого n. Как видим, латинские квадраты 2-го и 3-го порядков весьма просты. Впервые латинские квадраты 4-го порядка были рассмотрены в книге "Шамс аль Маариф" ("Книга о Солнце Гнозиса"), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году. Но определяющей вехой в истории исследований латинских квадратов стала работа Леонарда Эйлера, написанная им в последние годы жизни, "Recherches sur une nouvelle espece de quarres magiques"("Исследование, посвященное новым видам магических квадратов", 1782).

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

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях. Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9. 

Внимание Эйлера к латинским квадратам было вызвано изучением более сложных математических объектов — греко-латинских квадратов. Чтобы понять, что это такое, рассмотрим левый квадрат на рисунке 2.   

Рисунок 2. Греко-латинский квадрат (справа), образованный наложением

двух латинских квадратов (левого и центрального)

В шестнадцати ячейках этого квадрата расположены латинские буквы a, b, c и d таким образом, что каждая буква появляется один раз в каждом ряду и один раз в каждой колонке. В центре рисунка изображен другой латинский квадрат, ячейки которого обозначены соответствующими греческими буквами. Если мы совместим эти квадраты, что показано на рисунке справа, то увидим, что каждая латинская буква соединяется с каждой греческой буквой один единственный раз. Когда таким образом можно объединить два или более латинских квадрата, то они называются взаимно-ортогональными. Именно такие объединенные квадраты известны как греко-латинские. 

Правый квадрат на рисунке 2 дает одно из решений популярной карточной задачи XVIII века: 

Возьмите из карточной колоды всех тузов, королей, дам, валетов и расположите их в квадрате так, чтобы каждый ряд и каждая колонка содержали все четыре наименования и все четыре масти.

Читатель может поискать другое решение, удовлетворяющее условию, чтобы две главные диагонали содержали все четыре масти и все четыре наименования (см. в конце статьи). 

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

Рисунок 3. Четыре взаимно-ортогональных латинских квадрата 5-го порядка

Еще во времена Эйлера было доказано, что греко-латинские квадраты 2-го порядка не существуют. Были известны квадраты 3-го, 4-го и 5-го порядков. Ну а что можно сказать о квадратах 6-го порядка? Эйлер сформулировал этот вопрос в виде "задачи о 36 офицерах":

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

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

У меня нет сомнений в том, что невозможно построить квадрат с 36 ячейками. То же верно и для n = 10, n = 14 и вообще для всех чисел, не кратных 4.

Этот вывод получил известность как гипотеза Эйлера. Эту мысль можно выразить следующим образом:

для любых положительных целых чисел k не существует пар ортогональных латинских квадратов порядка n = 4k + 2. 

Заключительное предложение упомянутой выше научной работы Эйлера гласит:

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

В 1901 году французский математик Гастон Тьерри опубликовал доказательство того, что гипотеза Эйлера верна для квадратов 6-го порядка. Тьерри со своим братом проделал огромную работу. Он составил каталог всех возможных вариантов построения латинского квадрата 6-го порядка, а затем показал, что никакие пары не образуют греко-латинский квадрат. Это, конечно, подкрепило гипотезу Эйлера. Несколько математиков даже опубликовали "исчерпывающие доказательства" того, что гипотеза верна, но позже в этих доказательствах были обнаружены ошибки.

История гипотезы Эйлера является знаменательным примером единства науки — ведь начальный импульс, который привел к ее решению, выдвинут практическими нуждами планирования экспериментирования. Исследования, которые сам Эйлер считал бесполезными, оказывается, имеют огромную ценность во многих отраслях науки.

Сэр Рональд Фишер, профессор генетики Калифорнийского университета и один из ведущих мировых статистиков и биологов своего времени, был первым, кто еще в начале 1920-х годов показал, как использовать латинские квадраты в аграрных исследованиях.

Предположим, что необходимо испытать при минимальных затратах времени и средств влияние на рост пшеницы семи сельскохозяйственных химикатов. Одной из существенных трудностей при испытаниях такого рода является то, что плодородие различных участков почвы обычно зависит от случайных факторов. Каким образом можно спланировать эксперимент, который позволит испытать одновременно все семь химикатов и в то же самое время ограничить любые посторонние влияния, обусловленные случайными факторами? Ответ: разделите пшеничное поле на делянки, которые будут представлять ячейки квадрата со стороной в семь ячеек, затем примените семь "обработок" по модели случайно выбранного латинского квадрата. Благодаря наличию модели, простой статистический анализ результатов ограничит любые ошибки, обусловленные случайными изменениями плодородия почвы.

А теперь предположим, что вместо одного сорта пшеницы необходимо испытать семь. Можно ли спланировать такой эксперимент, который позволит учесть эти четыре переменных? (Остальные три переменных отражаются плодородием рядов, плодородием колонок и видом обработки.) Теперь для получения ответа используется греко-латинский квадрат. Греческие буквы покажут, где разместить семь сортов пшеницы, а латинские буквы – где применить семь различных химикатов. И в этом случае статистический анализ результатов не будет представлять сложности.

В наше время греко-латинские квадраты широко используются для планирования экспериментов в биологии, медицине, социологии и даже маркетинге. Конечно, "делянки" уже не будут участками почвы. Они могут представлять коров, пациентов, листья, клетки с животными, место для введения инъекций, период времени и даже наблюдателя или группу наблюдателей. Греко-латинский квадрат является просто моделью эксперимента. Его ряды представляют одну из переменных, колонки – другую, латинские буквы – третью, а греческие буквы – четвертую.

К примеру, исследователь-медик может спланировать эксперимент по влиянию пяти различных медикаментов на пациентов пяти различных возрастных групп, пяти различных весовых групп и пяти различных стадий одной и той же болезни. Наиболее эффективной конструкцией, которую может использовать исследователь в данном случае, является греко-латинский квадрат 5-го порядка, отобранный случайным образом из всех возможных квадратов этого порядка. При необходимости исследования влияния большего количества переменных можно использовать наложение дополнительных латинских квадратов, хотя для любого порядка n существует не больше n – 1 взаимно ортогональных квадратов. 

Не смотря на то, что на заре ХХ века гипотеза Эйлера была подтверждена для латинских квадратов 6-го порядка, до полной ясности было еще далеко. Дело в том, что с увеличением порядка квадрата объем работы по нахождению решения путем полного перебора возможных вариантов быстро возрастает.

В 1959 году анализ квадрата 10-го порядка был почти за пределами возможностей компьютеров. В Калифорнийском университете математики из Лос-Анджелеса запрограммировали компьютер (программа называлась SWAC) для исследования греко-латинских квадратов 10-го порядка. Более 100 часов работы компьютера не принесли успеха в построении даже одного квадрата. Результаты исследования составили такую микроскопическую долю общих случаев, что было невозможно сделать какие-либо выводы. Было установлено, что если гипотеза Эйлера и верна, то для того, чтобы ее доказать с применением программы SWAC, потребуется, по крайней мере, столетняя работа самого быстродействующего на тот момент компьютера. Но все оказалось не так безнадежно.

История о том, как Паркер, Боуз и Шрикханде сумели найти греко-латинские квадраты порядка 10, 14, 18, 22 и т.д., началась в 1958 году, когда Паркер сделал открытие, подвергавшее серьезному сомнению правильность гипотезы Эйлера. Вслед за Паркером Боуз разработал несколько общих правил построения греко-латинских квадратов больших порядков. Применив эти правила, Боуз и Шрикханде получили теоретическую возможность построить греко-латинский квадрат 22-го порядка. Так как 22 является четным числом, не делящемся на 4, гипотеза Эйлера была опровергнута. 

Интересно отметить, что методика построения этого квадрата была основана на решении сформулированной Киркманом известной задачи занимательной математики под названием "Задача про школьниц". В 1850 году Т.П. Киркман предложил такую задачу:

Школьная учительница по заведенному порядку выводит своих 15 девочек на дневную прогулку, всегда выстраивая их по три в пять рядов. Задача заключается в том, чтобы в течение 7 учебных дней выстраивать девочек так, что ни одна из них не гуляла больше одного раза в одном и том же ряду с любой другой девочкой.

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

Когда Паркер познакомился с результатами, полученными Боузом и Шрикханде, ему удалось разработать новый метод, применение которого привело к построению греко-латинского квадрата 10-го порядка. Первый "настоящий", а не теоретический, как у Боуза и Шрикханде, греко-латинский квадрат, в существование которого не верил сам Леонард Эйлер, был получен. Этот квадрат изображен на рисунке 4.

Рисунок 4. Греко-латинский квадрат Е.Т. Паркера 10-го порядка

является контрпримером гипотезы Эйлера

Символами одного латинского квадрата являются цифры от 0 до 9, расположенные слева в каждой ячейке квадрата. Цифры в правой стороне каждой ячейки принадлежат второму латинскому квадрату. С помощью этого квадрата, само существование которого отрицалось во многих учебниках по экспериментальным методам, статистики теперь могли планировать эксперименты с четырьмя наборами переменных, для которых можно легко установить и эффективно регулировать десять различных значений каждой переменной. 

Обратим внимание на то, что квадрат 3-го порядка в правом нижнем углу квадрата 10-го порядка является греко-латинскими квадратом. Все построенные Паркером квадраты 10-го порядка содержали подквадраты 3-го порядка. В течение какого-то времени вопрос о том, все ли греко-латинские квадраты 10-го порядка имеют подквадраты 3-го порядка, оставался открытым, но он был снят после открытия множества квадратов, не обладающих такими свойствами.

В результате интенсивной переписки между Боузом и Шрикханде с одной стороны и Паркером — с другой, методика все больше и больше совершенствовалась, и, в конце концов, было установлено, что гипотеза Эйлера ошибочна для всех значений n = 4k + 2, где n больше 6.

Фото из статьи в газете New York Times от 26 апреля 1959 об исторической работе

Е.Т. Паркера, С.С. Шрикханде и Р.С. Боуза

Внезапность, с которой была разрешена проблема, почти два столетия ставившая математиков в тупик, поразила авторов сильнее всего. Еще больше поражает то, что применявшаяся при этом концепция даже близко не приближалась к глубинам современной математики.  

Журнал Scientific American

ноябрь 1959 года

Обложка журнала Scientific American за ноябрь 1959 года воспроизводит интересное художественное полотно. Его создала художник журнала Эми Казаи. На картине изображен греко-латинский квадрат 10-го порядка (см. рис. 4). Десять цифр квадрата были заменены десятью различными красками, так что каждая ячейка окрашена соответствующей парой красок. 

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

Удивительно, но с первым греко-латинским квадратом 10-го порядка связана история появления в 1978 году одной из самих известных книг прошлого столетия — романа Жоржа Перека "Жизнь. Способ употребления". В ходе опроса, проведенного крупнейшей сетью книжных магазинов Франции FNAC и редакцией ежедневной Le Monde, роман занял 43-e место среди Лучших книг XX века по мнению французских читателей.

В 1960 году в Париже математиком Франсуа Ле Лионне и писателем Раймоном Кено была основана группа OULIPO (Ouvroir de littеrature potentielle — Цех потенциальной литературы). Это объединение писателей и математиков, поставившее своей целью научное исследование потенциальных возможностей языка путём изучения известных и создания новых искусственных литературных ограничений, под которыми понимаются любые формальные требования к художественному тексту с использованием математических средств.

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

Участники OULIPO предложили в строках квадрата расположить рассказываемые истории, в столбцах — персонажей (как то мсье Демэйзон, Поль, мадам Демэйзон, граф Белерваль, Архимед, Красная рыба, Судьба, Валерия, Дон Диего, мсье Мэмбр), латинские буквы будут определять их характер (a — страстно влюбленный, b — набитый дурак, c — каналья, греческие буквы или просто цифры — основные их действия (0 — не делает ничего, 1 — вор и убийца, 2 — ведет себя странным и необъяснимым образом и т.д.).

С 1966 года участником OULIPO стал французский писатель и кинорежиссер Жорж Перек и, проникся идеями соединения средств литературы и математики. 

В основу своего романа Ж. Перек положил греко-латинский квадрат десятого порядка, обозначающий сто комнат отеля, которые по ходу сюжета обходят «ходом коня». Этот роман, как поясняет автор, родился из трех независимых набросков — идеи о романе в форме греко-латинского квадрата; рисунка фасада парижского дома; головоломки-пазла, представляющего порт де ля Рошель. Объединение этих трех отправных точек случилось неожиданно, когда Ж. Перек рассматривал отражение рисунка дома в бокале, и схема греко-латинского квадрата неожиданно совпала с ним, каждая комната строения стала квадратиком и главой книги, перестановки, порожденные схемой, определили составные элементы каждой главы — мебель, обстановку, персонажей, географические и исторические отсылки, литературные аллюзии, цитаты и так далее. 

Роман представляет собой описание жилого дома в Париже под № 11 по несуществующей улице Симона Крюбелье и состоит из последовательного методичного и кропотливого описания помещений с населяющими их предметами и жильцами. Роман, писавшийся более 10 лет, состоит из 99 глав, 107 разных историй и описывает 1467 персонажей. По замыслу автора, роман можно читать с любого места, выбрать любой этаж, следить за любым отдельно взятым жильцом, выдернув из повествования отдельную историю. После публикации черновиков романа, стало известно, что все события романа были предопределены автором с самого начала, выстраивание романа подчинялось строгому плану, последовательность описаний соответствует ходам шахматного коня, ситуации, предметы, цвета распределяются согласно комбинаторным правилам и т.д. 

По мнению итальянского писателя Итало Кальвино (1923–1985), шедевр Перека стал перекрестком всех исканий литературы XX века. Перек стал одним из наиболее странных литературных деятелей мира, не похожим абсолютно ни на кого.

В последующие 1960-е годы и далее наряду с мастерством математиков по разработке наиболее эффективных методов программирования стремительно возрастало и быстродействие компьютеров. Используя рекуррентные методы, Паркер разработал программу для компьютера UNIVAC 1206 и смог провести обработку данного латинского квадрата 10-го порядка, завершив всестороннее исследование всех его ортогональных компаньонов в течение 28 – 45 минут машинного времени. Это улучшило производительность, достигнутую на старой программе SWAC, приблизительно в триллион раз! Итог — построение сотен новых греко-латинских квадратов 10-го порядка. Оказалось, что такие квадраты вполне обычны. С помощью UNIVAC нашлись ортогональные напарники для более чем половины построенных случайным образом латинских квадратов 10-го порядка. Паркер писал:

Таким образом, Эйлер ошибался в сильной степени, и полученные ранее факты свидетельствуют только о том, что это исследование требует большого объема вычислений.

Серьезное разочарование дальнейших компьютерных исследований греко-римских квадратов заключается в том, что до сих пор не найдено ни одного триплета взаимно ортогональных латинских квадратов 10-го порядка. Ранее было доказано, что для любого порядка n наибольшее возможное числа взаимно ортогональных латинских квадратов равно n – 1. Набор n – 1 таких квадратов известен как "полный набор". 

Например, латинский квадрат 2-го порядка имеет полный набор, состоящий из самого квадрата: 

Рисунок 5. Полный набор латинских квадратов 2-го порядка

Квадрат 3-го порядка имеет полный набор из двух ортогональных квадратов: 

 Рисунок 6. Полный набор латинских квадратов 3-го порядка

Квадрат 4-го порядка – из трех:

Рисунок 7. Полный набор латинских квадратов 3-го порядка

Полный набор четырех взаимно ортогональных латинских квадратов 5-го порядка представлен на рисунке 3. (Любая их пара может быть объединена для образования греко-латинского квадрата.) Однако полного набора 6-го порядка не существует даже в паре. Для порядков 7, 8 и 9 полные наборы существуют.

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

Этот вопрос приобретает дополнительный интерес в связи с возможностью построения "конечной проективной плоскости". Было показано, что если существует полный набор взаимно-ортогональных латинских квадратов для данного порядка n, то это дает возможность вывести конструкцию конечной проективной плоскости n-го порядка.

И наоборот, если известна конечная проективная плоскость для порядка n, можно построить полный набор взаимно-ортогональных латинских квадратов n-го порядка. Поскольку Тьерри доказал невозможность существования даже двух ортогональных латинских квадрата 6-го порядка, то невозможны и конечные проективные плоскости 6-го порядка. Полные наборы и конечные проективные плоскости существуют для порядков 2, 3, 4, 5, 7, 8 и 9. Не было ни доказано, ни опровергнуто существования конечных проективных плоскостей 10-го порядка. Поэтому открытие полного набора девяти латинских квадратов 10-го порядка должно попутно обеспечить успех в разрешении проблемы конечных проективных плоскостей.

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

Этот рисунок демонстрирует один из способов размещения 16 карт таким образом, что ни одно старшинство и ни одна масть не встречаются дважды ни в каком ряду. То же верно и для главных диагоналей. Обратите внимание на то, что 4 карты в каждом углу, так же как и 4 центральные карты, образуют наборы, в которых присутствует каждое наименование и каждая масть. Было бы интересно, если бы это решение обеспечивало чередование цветов типа шахматной доски, но это невозможно в принципе. 

Если рассматривать только ряды и колонки, но не главные диагонали, то можно найти решения, при которых цветовые варианты похожи на шахматную доску. Адольф Карфункель из Нью-Йорка предложил несколько таких решений, одно из которых приведено ниже. Можно без труда получить и другие решения, поменяв на предыдущем рисунке ряды 3 и 4, а также 1 и 2. 

Использованные источники: М. Гарднер "Новые математические развлечения" (Москва, АСТ, 2008), Н. Макарова "Группы взаимно ортогональных латинских квадратов", записи в liveinternet.ru, сайт www.cecm.sfu.ca и Википедия. 

  <<< Назад

Меланхолия и магический квадрат

Леонард Эйлер