История математики заполнена прозорливыми догадками — интуитивными гипотезами людей с большой математической интуицией. Часто эти гипотезы в течение столетий ждут своего доказательства или опровержения. Когда же, в конце концов, они появляются, то становятся математическими событиями первой величины. Об одном таком событии докладывалось в апреле 1959 года на ежегодной встрече Американского математического общества. Это опровержение известной гипотезы великого математика Леонарда Эйлера.
Леонард Эйлер (1707–1783 )
Эйлер был убежден, что греко-латинские квадраты определенных порядков теоретически не существуют. Три математика — Е.Т. Паркер, Р.С. Боуз и С.С. Шрикханде — полностью опровергли гипотезу Эйлера. Они разработали методы построения нескольких квадратов, существование которых, по мнению последователей Эйлера, 177 лет считалось невозможным.
Но с подробностями следует повременить, познакомимся сперва с основным предметом этой статьи. Итак, знакомьтесь.
Латинские и греко-латинские квадраты
Рисунок 1. Примеры латинских квадратов 2-го и 3-го порядков
Внимание Эйлера к латинским квадратам было вызвано изучением более сложных математических объектов — греко-латинских квадратов. Чтобы понять, что это такое, рассмотрим левый квадрат на рисунке 2.
Правый квадрат на рисунке 2 дает одно из решений популярной карточной задачи XVIII века:
Возьмите из карточной колоды всех тузов, королей, дам, валетов и расположите их в квадрате так, чтобы каждый ряд и каждая колонка содержали все четыре наименования и все четыре масти.
Читатель может поискать другое решение, удовлетворяющее условию, чтобы две главные диагонали содержали все четыре масти и все четыре наименования (см. в конце статьи).
Возможно существование и большего количества таких латинских квадратов, любая пара из которых ортогональна. На рисунке 3 изображено четыре взаимно-ортогональных латинских квадрата пятого порядка, для которых в качестве символов использованы цифры.
Рисунок 3. Четыре взаимно-ортогональных латинских квадрата 5-го порядка
Гипотеза Эйлера
Еще во времена Эйлера было доказано, что греко-латинские квадраты 2-го порядка не существуют. Были известны квадраты 3-го, 4-го и 5-го порядков. Ну а что можно сказать о квадратах 6-го порядка? Эйлер сформулировал этот вопрос в виде «задачи о 36 офицерах»:
Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в каре так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания.
У меня нет сомнений в том, что невозможно построить квадрат с 36 ячейками. То же верно и для n = 10, n = 14 и вообще для всех чисел, не кратных 4.
Заключительное предложение упомянутой выше научной работы Эйлера гласит:
На этом я заканчиваю свои исследования вопроса, который, хотя сам по себе полезен мало, приводит нас к довольно важным результатам комбинаторики, а также общей теории магических квадратов.
В 1901 году французский математик Гастон Тьерри опубликовал доказательство того, что гипотеза Эйлера верна для квадратов 6-го порядка. Тьерри со своим братом проделал огромную работу. Он составил каталог всех возможных вариантов построения латинского квадрата 6-го порядка, а затем показал, что никакие пары не образуют греко-латинский квадрат. Это, конечно, подкрепило гипотезу Эйлера. Несколько математиков даже опубликовали «исчерпывающие доказательства» того, что гипотеза верна, но позже в этих доказательствах были обнаружены ошибки.
Мало полезный вопрос
История гипотезы Эйлера является знаменательным примером единства науки — ведь начальный импульс, который привел к ее решению, выдвинут практическими нуждами планирования экспериментирования. Исследования, которые сам Эйлер считал бесполезными, оказывается, имеют огромную ценность во многих отраслях науки.
Сэр Рональд Фишер, профессор генетики Калифорнийского университета и один из ведущих мировых статистиков и биологов своего времени, был первым, кто еще в начале 1920-х годов показал, как использовать латинские квадраты в аграрных исследованиях.
Витраж с латинским квадратом 7-го порядка
в одном из колледжей Кембриджа, посвященный Р.Фишеру
Предположим, что необходимо испытать при минимальных затратах времени и средств влияние на рост пшеницы семи сельскохозяйственных химикатов. Одной из существенных трудностей при испытаниях такого рода является то, что плодородие различных участков почвы обычно зависит от случайных факторов. Каким образом можно спланировать эксперимент, который позволит испытать одновременно все семь химикатов и в то же самое время ограничить любые посторонние влияния, обусловленные случайными факторами? Ответ: разделите пшеничное поле на делянки, которые будут представлять ячейки квадрата со стороной в семь ячеек, затем примените семь «обработок» по модели случайно выбранного латинского квадрата. Благодаря наличию модели, простой статистический анализ результатов ограничит любые ошибки, обусловленные случайными изменениями плодородия почвы.
А теперь предположим, что вместо одного сорта пшеницы необходимо испытать семь. Можно ли спланировать такой эксперимент, который позволит учесть эти четыре переменных? (Остальные три переменных отражаются плодородием рядов, плодородием колонок и видом обработки.) Теперь для получения ответа используется греко-латинский квадрат. Греческие буквы покажут, где разместить семь сортов пшеницы, а латинские буквы – где применить семь различных химикатов. И в этом случае статистический анализ результатов не будет представлять сложности.
В наше время греко-латинские квадраты широко используются для планирования экспериментов в биологии, медицине, социологии и даже маркетинге. Конечно, «делянки» уже не будут участками почвы. Они могут представлять коров, пациентов, листья, клетки с животными, место для введения инъекций, период времени и даже наблюдателя или группу наблюдателей. Греко-латинский квадрат является просто моделью эксперимента. Его ряды представляют одну из переменных, колонки – другую, латинские буквы – третью, а греческие буквы – четвертую.
К примеру, исследователь-медик может спланировать эксперимент по влиянию пяти различных медикаментов на пациентов пяти различных возрастных групп, пяти различных весовых групп и пяти различных стадий одной и той же болезни. Наиболее эффективной конструкцией, которую может использовать исследователь в данном случае, является греко-латинский квадрат 5-го порядка, отобранный случайным образом из всех возможных квадратов этого порядка. При необходимости исследования влияния большего количества переменных можно использовать наложение дополнительных латинских квадратов, хотя для любого порядка n существует не больше n – 1 взаимно ортогональных квадратов.
И все-таки он существует!
Не смотря на то, что на заре ХХ века гипотеза Эйлера была подтверждена для латинских квадратов 6-го порядка, до полной ясности было еще далеко. Дело в том, что с увеличением порядка квадрата объем работы по нахождению решения путем полного перебора возможных вариантов быстро возрастает.
История о том, как Паркер, Боуз и Шрикханде сумели найти греко-латинские квадраты порядка 10, 14, 18, 22 и т.д., началась в 1958 году, когда Паркер сделал открытие, подвергавшее серьезному сомнению правильность гипотезы Эйлера. Вслед за Паркером Боуз разработал несколько общих правил построения греко-латинских квадратов больших порядков. Применив эти правила, Боуз и Шрикханде получили теоретическую возможность построить греко-латинский квадрат 22-го порядка. Так как 22 является четным числом, не делящемся на 4, гипотеза Эйлера была опровергнута.
Интересно отметить, что методика построения этого квадрата была основана на решении сформулированной Киркманом известной задачи занимательной математики под названием «Задача про школьниц». В 1850 году Т.П. Киркман предложил такую задачу:
Школьная учительница по заведенному порядку выводит своих 15 девочек на дневную прогулку, всегда выстраивая их по три в пять рядов. Задача заключается в том, чтобы в течение 7 учебных дней выстраивать девочек так, что ни одна из них не гуляла больше одного раза в одном и том же ряду с любой другой девочкой.
Эта задача является примером важного вида экспериментального построения, известного как «сбалансированные неполные блоки».
Когда Паркер познакомился с результатами, полученными Боузом и Шрикханде, ему удалось разработать новый метод, применение которого привело к построению греко-латинского квадрата 10-го порядка. Первый «настоящий», а не теоретический, как у Боуза и Шрикханде, греко-латинский квадрат, в существование которого не верил сам Леонард Эйлер, был получен. Этот квадрат изображен на рисунке 4.
Греко-латинский квадрат — квадрат N×N в каждой клетке которого стоят 2 числа от 1 до N так, что выполняются следующие условия:
Такие квадраты, как видно и из названия, тесно связаны с латинскими квадратами, для которых выполняется лишь первое правило, и в каждой ячейке которого стоит только одно число. Само название и тех и других квадратов пошло от Эйлера который использовал вместо цифр греческие и латинские буквы.
Греко-латинский квадрат можно рассматривать как наложение двух ортогональных латинских квадратов.
a
b
c
d
b
a
d
c
c
d
a
b
d
c
b
a
α
β
γ
δ
γ
δ
α
β
δ
γ
β
α
β
α
δ
γ
Греко-латинский квадрат, полученный наложением двух латинских квадратов выше
aα
bβ
cγ
dδ
bγ
aδ
dα
cβ
cδ
dγ
aβ
bα
dβ
cα
bδ
aγ
История
Занимаясь греко-латинскими квадратами Эйлер доказал, что квадратов второго порядка не существует, зато были найдены квадраты 3, 4, и 5 порядков. Квадрата 6 порядка обнаружить не удалось, но доказать, что их не существует, Эйлеру не удалось. Но им была высказана гипотеза, что не существует квадрата порядка N, если N — чётное число, не делящееся на 4 (то есть 6, 10, 14 и т. д.). В 1901 гипотеза была подтверждена для N=6 математиком Гастоном Терри. Это было сделано перебором всех возможных вариантов квадрата. А в 1959 году гипотеза была опровергнута Э. Т. Паркером, Р. К. Боусом и С. С. Шрикхердом, обнаружившими квадрат порядка 10
00
47
18
76
29
93
85
34
61
52
86
11
57
28
70
39
94
45
02
63
95
80
22
67
38
71
49
56
13
04
59
96
81
33
07
48
72
60
24
15
73
69
90
82
44
17
58
01
35
26
68
74
09
91
83
55
27
12
46
30
37
08
75
19
92
84
66
23
50
41
14
25
36
40
51
62
03
77
88
99
21
32
43
54
65
06
10
89
97
78
42
53
64
05
16
20
31
98
79
87
После были обнаружены квадраты 14, 18 и т. д. порядков.
Задачи о греко-латинских квадратах
Сам Эйлер поставил задачу о нахождении квадрата 6 порядка так:
В 6 полках есть 36 офицеров 6 различных званий. Нужно так разместить их в каре чтобы все офицеры в каждой колонне и шеренге были разных званий и из разных полков. Как уже было указано такая задача неразрешима.
Другая задача звучит так:
нужно разложить 16 карт (валеты, дамы, короли и тузы разных мастей) так чтобы в каждом ряду и столбце было по одной карте каждой масти и значения. Эта задача была известна ещё до Эйлера. Её решением будет любой греко-римский квадрат порядка 4. Также для этой задачи есть варианты в которых требуется, чтобы на главных диагоналях выполнялись те же требования. В другом варианте требуется чтобы цвета мастей шли в шахматном порядке. Все эти задачи имеют решения.
Применение греко-латинских квадратов
Если есть система, на которую действуют 4 различных параметра (например воздействие N различных рекламных роликов на население N различных возрастных, социальных и этнических групп), которые могут принимать по N значений нужно рассмотреть греко-латинский квадрат порядка N. Тогда параметры будут соответствовать ряду, столбцу, первому и второму числу. таким образом можно провести экспериментов, вместо (в случае полного перебора вариантов)
Греко-латинский квадрат — квадрат N×N в каждой клетке которого стоят 2 числа от 1 до N так, что выполняются следующие условия:
Такие квадраты, как видно и из названия, тесно связаны с латинскими квадратами, для которых выполняется лишь первое правило, и в каждой ячейке которого стоит только одно число. Само название и тех и других квадратов пошло от Эйлера который использовал вместо цифр греческие и латинские буквы.
Греко-латинский квадрат можно рассматривать как наложение двух ортогональных латинских квадратов.
a
b
c
d
b
a
d
c
c
d
a
b
d
c
b
a
α
β
γ
δ
γ
δ
α
β
δ
γ
β
α
β
α
δ
γ
Греко-латинский квадрат, полученный наложением двух латинских квадратов выше
aα
bβ
cγ
dδ
bγ
aδ
dα
cβ
cδ
dγ
aβ
bα
dβ
cα
bδ
aγ
История
Занимаясь греко-латинскими квадратами Эйлер доказал, что квадратов второго порядка не существует, зато были найдены квадраты 3, 4, и 5 порядков. Квадрата 6 порядка обнаружить не удалось, но доказать, что их не существует, Эйлеру не удалось. Но им была высказана гипотеза, что не существует квадрата порядка N, если N — чётное число, не делящееся на 4 (то есть 6, 10, 14 и т. д.). В 1901 гипотеза была подтверждена для N=6 математиком Гастоном Терри. Это было сделано перебором всех возможных вариантов квадрата. А в 1959 году гипотеза была опровергнута Э. Т. Паркером, Р. К. Боусом и С. С. Шрикхердом, обнаружившими квадрат порядка 10
00
47
18
76
29
93
85
34
61
52
86
11
57
28
70
39
94
45
02
63
95
80
22
67
38
71
49
56
13
04
59
96
81
33
07
48
72
60
24
15
73
69
90
82
44
17
58
01
35
26
68
74
09
91
83
55
27
12
46
30
37
08
75
19
92
84
66
23
50
41
14
25
36
40
51
62
03
77
88
99
21
32
43
54
65
06
10
89
97
78
42
53
64
05
16
20
31
98
79
87
После были обнаружены квадраты 14, 18 и т. д. порядков.
Задачи о греко-латинских квадратах
Сам Эйлер поставил задачу о нахождении квадрата 6 порядка так:
В 6 полках есть 36 офицеров 6 различных званий. Нужно так разместить их в каре чтобы все офицеры в каждой колонне и шеренге были разных званий и из разных полков. Как уже было указано такая задача неразрешима.
Другая задача звучит так:
нужно разложить 16 карт (валеты, дамы, короли и тузы разных мастей) так чтобы в каждом ряду и столбце было по одной карте каждой масти и значения. Эта задача была известна ещё до Эйлера. Её решением будет любой греко-римский квадрат порядка 4. Также для этой задачи есть варианты в которых требуется, чтобы на главных диагоналях выполнялись те же требования. В другом варианте требуется чтобы цвета мастей шли в шахматном порядке. Все эти задачи имеют решения.
Применение греко-латинских квадратов
Если есть система, на которую действуют 4 различных параметра (например воздействие N различных рекламных роликов на население N различных возрастных, социальных и этнических групп), которые могут принимать по N значений нужно рассмотреть греко-латинский квадрат порядка N. Тогда параметры будут соответствовать ряду, столбцу, первому и второму числу. таким образом можно провести экспериментов, вместо (в случае полного перебора вариантов)
экспериментов, вместо 
(в случае полного перебора вариантов)