Теория Рамсея

Талантливый математик Фрэнк Пламптон Рамсей доказал, что полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру

Рональд Л. Грэм, Джоуэл X. Спенсер

Как повествует написанный три с половиной тысячи лет назад клинописный текст, однажды древнешумерский учёный взглянул на звёздное небо и увидел льва, буйвола и скорпиона. Современный астроном скорее всего склонен описывать созвездие как временную группу звёзд, которую мы, земляне, наблюдаем с одной точки на краю обычной галактики. И всё же большинство любителей поглазеть на звёзды согласятся, что ночное небо выглядит сплошь усыпанным созвездиями, имеющими форму прямых линий, четырёхугольников и пятиугольников. Может ли так быть, что подобные геометрические фигуры порождаются какими-то неизвестными нам силами, действующими во Вселенной?

Математика предлагает куда более простое объяснение. В 1928году Фрэнк Пламптон Рамсей, английский математик, философ и экономист, доказал, что такие упорядоченные конфигурации неизбежно присутствуют в любой большой структуре, будь то группа звёзд, совокупность случайно разбросанных камешков или последовательность чисел, полученных бросанием игральной кости. Если речь идёт о достаточно большом количестве звёзд, то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию: прямую линию, прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактически теория Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру. Как впервые провозгласил около четверти века назад умерший недавно американский математик Теодор С.Моцкин, из теории Рамсея следует, что полный беспорядок невозможен.

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

В отличие от многих разделов современной математики теорию Рамсея можно изложить на интуитивном уровне. В самом деле, привлекательность этой теории отчасти обусловлена той простотой, с которой можно сформулировать её задачи. Например, если из присутствующих на вечеринке случайным образом выбрать шесть человек (скажем, Альфреда, Бетти, Кэлвина, Дебору, Эдварда и Фрэнсис), то верно ли, что либо трое из них друг с другом знакомы, либо трое из них незнакомы друг с другом?

Мы можем решить эту «головоломку о вечеринке» многими способами. Мы могли бы перебрать все мыслимые комбинации и проверить, содержит ли каждая рассматриваемая группа трёх знакомых или трёх незнакомых людей. Но поскольку нам пришлось бы проверить 32768 (или 2¹⁵) комбинаций, то такой «метод грубой силы» не является ни практичным, ни поучительным.

К счастью, мы можем отыскать ответ, рассмотрев два простых случая. В первом из них предположим, что Альфред знает трёх (или больше) из числа остальных гостей, скажем, Бетти, Кэлвина и Дебору. Если Бетти и Кэлвин, или Бетти и Дебора, или Кэлвин и Дебора знакомы друг с другом, то Альфред и пара знакомых образуют группу из трёх знакомых людей; в противном случае Бетти, Кэлвин и Дебора друг с другом незнакомы. Во втором случае предположим, что Альфред знает самое большее двух (или меньше) из гостей, скажем, Бетти и Кэлвина. Если Дебора и Эдвард, или Дебора и Фрэнсис, или Эдвард и Фрэнсис незнакомы друг с другом, то Альфред и пара незнакомых между собой гостей образуют группу из трёх человек, незнакомых друг с другом. В противном случае Дебора, Эдвард и Фрэнсис друг с другом знакомы. Всего в шести предложениях мы доказали, почему любая группа из шести человек должна включать или трёх знакомых, или трёх незнакомых людей. Короче говоря, решение «головоломки о вечеринке» есть частный случай теории Рамсея.

Рис.1. Головоломка о вечеринке представляет собой задачу, типичную для приложений теории Рамсея. Какое количество людей достаточно для того, чтобы образовать группу, в которой всегда окажется либо четверо людей знакомых друг с другом, либо четверо, друг с другом незнакомых? На этом рисунке гости представлены точками. Каждое красное ребро на этом графе соединяет гостей, знакомых друг с другом, а каждое синее — незнакомых. В группе из 17 точек, изображённых на рисунке, невозможно найти четыре точки для которых сеть соединяющих их рёбер была бы целиком красной или целиком синей Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось либо четверо знакомых, либо четверо незнакомых друг с другом. На самом деле во всякой группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо незнакомых друг с другом.

Обобщая этот частный случай, мы можем сформулировать теорему в её полном виде. Вместо шести человек, как в этой задаче, мы можем взять любое число людей или, если хотите, любое число объектов. Кроме того, нет нужды ограничиваться двумя типами отношений, знакомства и незнакомства. Мы можем взять любое число взаимоисключающих отношений — например друзья, враги и соблюдающие нейтралитет.

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

Фрэнк Рамсей, впервые доказавший это утверждение в 1928году, вырос в Кембридже (Англия). Его отец, Артур С.Рамсей, был профессором математики и президентом колледжа Магдалины Кембриджского университета. В 1925году молодой Рамсей, признанный самым лучшим студентом в области математики, окончил университет. Хотя больше всего его интересовали философия и математическая логика, он также писал работы по экономике, теории вероятности, принятию решений, когнитивной психологии и семантике.

Вскоре после окончания университета он вошёл в группу экономистов, которую возглавлял Джон Мэйнард Кейнс. Рамсей написал лишь две статьи по математической экономике, но обе до сих пор широко цитируются. Что касается философии, то его вдохновляли идеи Джорджа И.Мура, Людвига Витгенштейна и Бертрана Рассела. Мур писал: «Он необычайно ясно мыслил: никто не мог легче его избежать тех логических погрешностей, от которых несвободны даже лучшие философы». Затем произошла трагедия: в 1930году Рамсей заболел и в 26лет умер от осложнений после операции.

Есть некая ирония в том, каким образом за два года до смерти Рамсей вывел теорию, ныне называемую его именем. Он пришёл к основной идее, пытаясь доказать тезис, выдвинутый Расселом и Альфредом Нортом Уайтхедом в их основополагающем труде «Principia Mathematica» (Основы математики). Они предположили, что все математические истины могут быть выведены из ограниченного набора аксиом. Развивая эту идею, немецкий математик Давид Гильберт предположил, что должна существовать процедура, позволяющая решить, следует ли то или иное утверждение из данного набора аксиом или нет. Рамсей показал, что в некотором частном случае такая процедура принятия решения существует. (Спустя несколько лет Курт Гёдель и его последователи, англичанин Алан Тьюринг и другие, исчерпывающим образом доказали, что в общем случае такой процедуры не существует.)

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

Так обстояли дела до 1933года, когда два венгерских математика, Пауль Эрдёш и Джордж Шекереш, заново открыли теорию Рамсея. В основном благодаря их усилиям эта теория стала популярной в среде математиков. В то время Эрдёш был девятнадцатилетним студентом Будапештского университета, а Шекереш незадолго до этого получил диплом инженера-химика в Будапештском политехническом институте. Вместе с группой друзей-студентов они почти каждое воскресенье встречались в загородном парке, в основном для разговоров о математике.

Зимой 1933года одна из студенток, Эстер Клейн, предложила друзьям решить любопытную задачу; доказать, что если пять точек на плоскости расположены таким образом, что никакие три точки не лежат на одной прямой, то обязательно найдутся четыре из них, образующие выпуклый четырёхугольник. (К выпуклым фигурам относится, скажем, правильный шестиугольник, но не относится пятиконечная звезда. Более строго, многоугольник называется выпуклым, если всякий отрезок, соединяющий его вершины, лежит внутри этого многоугольника.)

Позволив друзьям вдоволь поразмышлять над этой задачей, Клейн представила доказательство (см. рис.3).

1-Й СЛУЧАЙ	2-Й СЛУЧАЙ	3-Й СЛУЧАЙ

Рис.3. Теория Рамсея была заново открыта в 1933году, когда молодая студентка Эстер Клейн предложила следующую геометрическую задачу: доказать, что если пять точек расположены на плоскости и никакие три из них не лежат на одной прямой, то какие-нибудь четыре из них всегда образуют выпуклый четырёхугольник. Любая конфигурация, удовлетворяющая условиям задачи, относится к одному из трёх случаев, показанных на рисунке. Простейший случай — тот, когда выпуклая оболочка (т.е. выпуклый многоугольник, охватывающий все точки) есть четырёхугольник. Если выпуклая оболочка является пятиугольником, то любые четыре точки можно соединить так, что они образуют четырёхугольник. Треугольная выпуклая оболочка всегда содержит внутри две точки; здесь — D и E. Линия DE делит треугольник на две части так, что две точки, A и B, лежат по одну сторону от неё. Четыре точки ABCD должны образовывать выпуклый четырёхугольник.

Эрдёш и Клейн быстро нашли обобщение исходной задачи. Они поняли, что пять из девяти точек на плоскости всегда образуют выпуклый пятиугольник. Тогда они предложили новую задачу: если число точек на плоскости равно 1+2^k–2, где k=3, 4, 5 ... и т.д., то можно ли всегда выбрать k точек, образующих выпуклый многоугольник?

В своих воспоминаниях Шекереш так описывает последующие события: «Мы вскоре осознали, что простые рассуждения не подходят, и появилось волнующее чувство, что в нашем кружке впервые возник новый тип геометрических задач». Шекереш показал, что существует такое число n, что если n точек лежат на плоскости так, что никакие три из них не находятся на одной прямой, то среди них всегда можно найти k точек, образующих выпуклый k-угольник. Другими словами, если точек достаточно много, всегда можно найти их подмножество, образующее многоугольник с заданным числом сторон. Доказав это, Шекереш заново открыл теорему Рамсея, хотя никто из их группы в то время не знал о ней.

В 1934году Эрдёш и Шекереш опубликовали свои результаты, хотя ни они, ни кто-либо другой до сих пор не смогли доказать гипотезу Эрдёша о том, что числа точек n=1+2^k–2 достаточно. Эрдёш часто называет эту совместную публикацию «статьёй со счастливым концом», поскольку вскоре после её опубликования Шекереш и Клейн поженились. Эрдёш же стал самым продуктивным математиком нашего столетия.

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

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

Следовательно, если три человека знакомы друг с другом, то рёбра между соответствующими точками образуют красный треугольник, а если эти трое незнакомы, то образуется синий треугольник. Головоломку о вечеринке тогда можно сформулировать так: верно ли, что если каждое ребро, соединяющее любые две из шести точек, окрасить в синий или красный цвет произвольным образом, то всегда возникает либо синий, либо красный треугольник?

Задача, которую изучал Эрдёш, представляет собой обобщение этой задачи. Он определил полную сеть как набор точек, каждая из которых соединена рёбрами со всеми остальными. Затем он задался вопросом: какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержит полную сеть красного или синего цвета? Ответ следующий: полная сеть — из шести точек. Эту задачу и её решение удобнее выразить так: число Рамсея (R) для трёх красных и трёх синих равно шести.

А как насчет числа Рамсея для пяти красных и трёх синих? Другими словами, какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержала бы либо красную сеть из пяти точек, либо синюю сеть из трёх точек? Число Рамсея для пяти красных и трёх синих равно 14, что доказали только в 1955году Роберт Гринвуд из Университета шт.Техас в Остине и Эндрю Глисон из Гарвардского университета.

5 < R(3,3) = 6	8 < R(3,4) = 9	13 < R(3,5) = 14
17 < R(3,6) = 18		22 < R(3,7) = 23
27 < R(3,8) ≤ 29		35 < R(3,9) = 36

Рис.2. Числа Рамсея определяются как наименьшее значение n, для которого в любой группе из n точек либо некоторая группа из j точек образует полную сеть красных рёбер, либо некоторая группа из k точек образует полную сеть синих рёбер. Рисунки показывают, как велико должно быть конкретное число Рамсея. На первой диаграмме изображены пять точек, соединённые красными и синими рёбрами таким способом, что никакие три точки не образуют ни красной, ни синей полной сети. Следовательно, из первой диаграммы можно вывести, что число Рамсея для трёх красных и трёх синих больше пяти. Аналогично можно утверждать, что из второй диаграммы следует, что число Рамсея для трёх красных и четырёх синих больше восьми. Другими более сложными методами можно показать, что число Рамсея для трёх красных и трёх синих равно шести, а число Рамсея для трёх красных и четырёх синих равно девяти. Все точно известные числа Рамсея приведены выше, кроме числа Рамсея для четырёх красных и четырёх синих, диаграмма для которого изображена на рис.1. (На некоторых диаграммах синие рёбра для простоты не показаны.) Относительно числа Рамсея для трёх красных и восьми синих было доказано, что оно больше 27 и меньше или равно 29. Недавно было показано (но пока не подтверждено), что оно равно 28.

Числа Рамсея чрезвычайно трудно вычислять. Усилиями поколений математиков и компьютеров удалось найти лишь семь чисел Рамсея, которые приведены на рис.2. Чтобы наглядно продемонстрировать трудность вычисления чисел Рамсея, Эрдёш часто рассказывает следующий анекдот. Инопланетяне вторглись на Землю и угрожают уничтожить её через год, если человечество не сможет найти число Рамсея для пяти красных и пяти синих. Мы могли бы мобилизовать лучшие умы и самые быстродействующие компьютеры, и тогда в течение года мы, возможно, сумели бы найти искомое значение. Однако если бы инопланетяне потребовали от нас найти число Рамсея для шести красных и шести синих, то у нас не осталось бы иного выбора, как нанести упреждающий удар.

Эрдёш всё же нашёл способ получить некоторое представление о том, насколько большим должно быть число Рамсея. Что если он сможет найти красно-синюю раскраску большой полной сети, не содержащую ни красной, ни синей сети из трёх точек? Такая раскраска полной сети из пяти точек показана на рис.2. Отсюда следует, что число Рамсея для трёх красных и трёх синих должно быть больше пяти. Пять есть нижняя граница для этого числа Рамсея.

В 1947году Эрдёш предложил необычный метод отыскания нижней границы любого числа Рамсея: бросание монеты. Он предпринял мысленный эксперимент, в котором каждое ребро полной сети из, скажем, миллиона точек окрашивалось в соответствии с результатом бросания «настоящей» монеты (т.е. монеты, для которой вероятность выпадения орла или решки строго одинакова и равна 1/2. — Перев.). Ребро окрашивается в красный цвет, если выпадает решка, и в синий, если выпадает орёл. Затем он попытался доказать, что число Рамсея, скажем, для 34 красных и 34 синих больше миллиона. Эксперимент считается успешным, если в результате такой случайной раскраски не образуется ни красной, ни синей сети из 34 точек.

Как бы он мог гарантировать успех? Любые 34 точки соединяются 561 ребром. Если первое бросание предписывает синий цвет для первого ребра, то для получения синей сети необходимо, чтобы следующие 560 бросаний тоже предписывали синий цвет. Вероятность того, что это произойдёт, равна 2^–561. Вероятность появления красной сети точно такая же, так что общая вероятность возникновения одноцветной сети вдвое больше, или примерно 2,6×10^–169.

Теперь вспомним, что число наборов из 34 точек, выбранных из миллиона точек, равно

1000000! 34! · 999966!

≈3,4×10165.

Тем самым можно ожидать, что из всех возможных полных сетей из 34 точек одноцветными будут 3,4×10¹⁶⁵×2,6×10^–169, или приблизительно 0,001. Итак, в 99,9% случаев мысленный эксперимент будет успешным, одноцветные наборы из 34 точек не возникнут.

Затем Эрдёш применил тонкое доказательство от противного. Он предположил, что никакая схема раскраски не является успешной. Тогда мысленный эксперимент будет иметь нулевую вероятность успеха, что, как ему уже известно, не соответствует действительности. Значит, это предположение должно быть ошибочным, т.е. должна существовать успешная схема раскраски (не с вероятностью 99,9%, а с абсолютной достоверностью). Существование такой раскраски означает, что один миллион является нижней границей для 34 красных и 34 синих.

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

Значительная часть ранних исследований по теории Рамсея была посвящена множествам точек и линий, но всё же во многих из них рассматривались и множества чисел. Голландский математик Бартель Л.Ван дер Варден начал решать такие задачи ещё до того, как Рамсей доказал свою теорему.

В 1926 году Ван дер Варден встретился с интересной задачей, связанной с арифметическими прогрессиями. Как следует из самого названия, арифметическая прогрессия — это такая последовательность чисел, в которой разность между двумя соседними членами остаётся постоянной. Например, последовательность 3, 5, 7 есть трёхчленная арифметическая прогрессия, в которой разность между соседними членами равна двум. Частный случай задачи, привлёкшей внимание Ван дер Вардена, можно сформулировать так. Если каждое целое число от 1 до 9 напечатать на странице одной из двух красок, красной или синей, то всегда ли найдутся три синих или три красных числа, образующие арифметическую прогрессию? Ответ даётся в следующей врезке.

Теория Рамсея и арифметические прогрессии

Арифметическая прогрессия — это последовательность чисел, в которой разность между соседними членами остаётся постоянной. Например, 7, 10, 13, 16 — это арифметическая прогрессия, в которой разность между соседними членами равна трём. Из теории Рамсея следует такое утверждение об арифметических прогрессиях: если каждое число от 1 до 9 покрасить в красный или синий цвет, то либо три синих числа, либо три красных образуют арифметическую прогрессию.

Чтобы доказать это утверждение, мы могли бы проверить все 512 способов раскраски девяти чисел. Но мы можем доказать его, рассмотрев только два случая. Начнём со случая, в котором 4 и 6 имеют одинаковый цвет, скажем синий.

1 2 3 4 5 6 7 8 9

Чтобы избежать синей арифметической прогрессии 4, 5, 6, мы покрасим 5 в красный цвет.

1 2 3 4 5 6 7 8 9

Чтобы избежать синих арифметических прогрессий 2, 4, 6 и 4, 6, 8, мы покрасим 2 и 8 в красный цвет.

1 2 3 4 5 6 7 8 9

Но тогда у нас получится красная арифметическая прогрессия 2, 5, 8. Итак, если 4 и 6 имеют одинаковый цвет, то всегда получится либо красная, либо синяя арифметическая прогрессия. Теперь рассмотрим случай, когда 4 и 6 имеют различный цвет. Число 5 можно покрасить как угодно, не создав при этом арифметической прогрессии, так что мы произвольно покрасим 5 в красный цвет.

1 2 3 4 5 6 7 8 9

Продолжим раскрашивание следующим образом:

3, чтобы избежать 3 4 5

9, чтобы избежать 3 6 9

7, чтобы избежать 5 7 9

8, чтобы избежать 6 7 8

2, чтобы избежать 2 5 8

1, чтобы избежать 1 2 3

Такое раскрашивание даёт последовательность

1 2 3 4 5 6 7 8 9

Но в ней всё равно осталась красная арифметическая прогрессия 1, 5, 9. Таким образом, независимо от того, в одинаковый или в разные цвета окрашены 4 и 6, всегда имеется либо синяя, либо красная арифметическая прогрессия.

Ван дер Варден поставил перед собой следующую задачу, являющуюся обобщением предыдущей: доказать, что если n — достаточно большое число и все целые числа от 1 до n напечатаны на странице одним из двух произвольно выбираемых для каждой цифры цветов, то всегда существует одноцветная последовательность с определённым числом членов, являющаяся арифметической прогрессией. Это утверждение можно считать теоремой Рамсея для арифметических последовательностей, хотя оно общеизвестно под названием теоремы Ван дер Вардена.

Ван дер Варден призвал на помощь своих коллег Эмиля Артина и Отто Шрейера. Позднее он писал: «Мы пришли в кабинет Артина на факультет математики Гамбургского университета и попытались найти доказательство. Мы рисовали на доске какие-то рисунки. У нас было состояние, которое немцы называют Einfälle (озарение), когда в голову приходят неожиданные идеи. Несколько раз такие новые идеи направляли обсуждение в новое русло, и одна из них в конце концов привела к решению». Оказалось, однако, что Ван дер Варден не смог доказать этот результат для двух красок, не доказав его для случая, когда одновременно используется произвольное число красок.

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

Чтобы доказать теорему Рамсея для арифметических прогрессий, Ван дер Варден применил более тонкую, двойную индукцию. Он предположил, что для любого фиксированного числа красок существует число n, такое, что если каждое целое число в интервале от одного до n напечатать какой-нибудь из этих красок, то найдётся арифметическая прогрессия чисел одного цвета, состоящая, скажем, из 10 членов. Опираясь на это допущение, он смог показать, что для любого фиксированного набора красок существует число m, такое, что если каждое целое число в интервале от 1 до m напечатать какой-нибудь из этих красок, то будет существовать одноцветная арифметическая прогрессия из 11 членов. В общем, он показал, что из результатов для k членов и любого количества красок вытекает результат для k+1 членов и любого количества красок.

После того как Ван дер Варден добрался до этой стадии доказательства, ему осталось только продемонстрировать, что его предположение действительно верно для некоторого малого значения k. Если целых чисел на единицу больше, чем красок, то всегда найдутся два числа одного цвета. Эти два числа образуют арифметическую прогрессию из двух членов. Поэтому одноцветная арифметическая прогрессия всегда существует, если чисел на единицу больше, чем красок. Бесконечная последовательность фишек домино для двух членов теперь сталкивает бесконечную последовательность домино для трёх членов, которая, в свою очередь, сталкивает бесконечную последовательность домино для четырёх членов, и так далее (см. следующую врезку).

Теория Рамсея и игра «крестики-нолики»

В 1926году Бартель Л. Ван дер Варден доказал, что если n — достаточно большое число и если все числа от 1 до n произвольным образом раскрасить каким-нибудь из двух цветов, то всегда найдётся одноцветная арифметическая прогрессия с определённым числом членов. В 1963году А.Хейлз и Р.Джуитт открыли то, что оказалось сутью теоремы Ван дер Вардена, изучая игру «крестики-нолики». Хотя классический вариант этой игры с игровым полем размером три на три может быстро наскучить, трёхмерный вариант с четырьмя полями в каждом ряду весьма интересен. «Доской» для трёхмерной игры служит куб, разбитый на 64 ячейки. Игроки по очереди заполняют ячейки крестиками или ноликами, пока один из них не выигрывает, заполнив четыре ячейки, расположенные на одной прямой. И двумерная, и трёхмерная игра порой кончается ничьей. А как обстоит дело в случае игр более высокой размерности? Можно ли гарантировать выигрыш в некотором n-мерном варианте крестиков и ноликов с k элементами на одной прямой?

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

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

Координаты крестиков в этой выигрышной комбинации суть 121, 222 и 323; рассматриваемые как числа, они образуют арифметическую прогрессию. Можно показать, что всякая выигрышная комбинация, преобразованная этим методом, даёт арифметическую прогрессию.

1

1

2 ×

3

1 2 3

2

1

2 ×

3

1 2 3

3

1

2 ×

3

1 2 3

Доказав теорему Рамсея для арифметических прогрессий, Ван дер Варден применил эти знания к решению следующей задачи. Каково наименьшее значение n, гарантирующее существование одноцветной арифметической последовательности из, скажем, 10 членов, если каждое число от 1 до n напечатать любой произвольно выбранной из двух красок? Лучший ответ, который Ван дер Варден смог найти, выражался столь большим числом, что его невозможно было записать в обычном виде. Оно было больше миллиарда, больше чем 10 в степени миллиард.

В самом деле, чтобы выразить его результат, математики прибегают к последовательности функций, известной как иерархия Аккермана. Первая функция в этой иерархии называется просто DOUBLE(x). Как подсказывает название (double — значит, удвоить), эта функция удваивает значение x. Так DOUBLE(1) равно 2, DOUBLE(50) равно 100. Вторая функция, EXPONENT(x), может быть описана как 2 в степени x, и, следовательно, EXPONENT(3) равно 8. Можно также выразить EXPONENT через DOUBLE. Например, чтобы найти EXPONENT(3), мы удваиваем 1, затем удваиваем результат предыдущего действия и затем снова удваиваем результат. На самом деле любая функция в иерархии Аккермана определяется через предыдущую.

Итак, третью функцию этой иерархии, TOWER(x), можно выразить с помощью функции EXPONENT. TOWER(3), например, — это 2 в степени 2 в степени 2, что равно 2 в степени 4, т.е. 16. TOWER(x) иногда записывают в виде «башни» (tower — значит, башня) показателей степеней,

		2...2
2	2

где x — число двоек в этой башне. Но даже функция TOWER(x) растёт недостаточно быстро, чтобы можно было записать результат Ван дер Вардена.

Следующую функцию, известную под шуточным прозвищем WOW(x) (английское междометие WOW примерно соответствует русским «Ой!», «Ах!» и «Ну и ну!». — Перев.), можно найти, если начать с 1 и применить x раз функцию TOWER. Тогда,

WOW(1) = TOWER(1) = 2, WOW(2) = TOWER(2) = 4, WOW(3) = TOWER(4) = 65536.

Чтобы найти WOW(4), нужно вычислить TOWER(65536). Чтобы это сделать, нужно начать с 1 и применить функцию EXPONENT 65536 раз. Даже применение функции EXPONENT всего лишь пять раз даёт 2⁶⁵⁵³⁶, — число, которое, будучи записанным цифра за цифрой, заполнило бы две страницы этого журнала. На самом деле даже число, заполняющее все страницы всех книг и всю память всех компьютеров, всё же останется несравнимым с WOW(4).

Тем не менее, чтобы всё-таки записать результат Ван дер Вардена, придётся определить функцию, которая растёт ещё быстрее. Функция ACKERMANN(x) определяется последовательностью DOUBLE(1), EXPONENT(2), TOWER(3), WOW(4) и так далее. ACKERMANN(x) в конце концов растёт быстрее любой функции в этой иерархии. Доказательство Ван дер Вардена даёт следующий количественный результат: если числа 1, 2, ..., ACKERMANN(k) раскрашены двумя красками, то всегда существует одноцветная арифметическая прогрессия длиной k.

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

В 1987году, однако, израильский логик Саарон Шела из Еврейского университета в Иерусалиме добился крупного успеха. Шела широко признан как человек, лучше всех справляющийся с решением сложнейших задач в современной математике. Он сумел преодолеть барьер функции ACKERMANN и показал следующее: если целые числа от 1 до WOW(k) раскрасить в два цвета, то всегда найдётся одноцветная арифметическая прогрессия длиной k членов.

Несмотря на свою специализацию, Шела вовсе не использует в своём доказательстве каких-либо средств математической логики. В нём применены лишь элементарные (но чрезвычайно остроумные) математические идеи. Полностью выписанное, его доказательство занимает приблизительно четыре страницы, и большинство специалистов находит его более чётким, чем первоначальное доказательство Ван дер Вардена. Что самое важное, он обошёлся без двойной индукции. Он фиксирует число красок на двух (или любом другом конкретном значении) и затем проводит обычную индукцию: если утверждение верно для прогрессий длиной k членов, то оно также справедливо и для прогрессий длиной k+1.

Математики сейчас пытаются понять, можно ли улучшить доказательство Шелы, чтобы получить для теоремы Ван дер Вардена оценку порядка TOWER или даже EXPONENT. Один из нас (Грэм) предложил премию в размере 1000 долларов тому, кто докажет (или опровергнет) утверждение, что для всякого k раскрашенная в два цвета совокупность чисел от 1 до TOWER(k) содержит одноцветную арифметическую прогрессию из k членов.

Усилиями Рамсея, Эрдёша, Ван дер Вардена и многих других были заложены основы теории, носящей имя Рамсея. Пока что исследователи только начали изучать следствия этой теории. Она позволяет предположить, что структурная основа математики состоит из чрезвычайно больших чисел и множеств — объектов столь громадных, что их трудно даже выразить, а тем более постичь.

Когда мы научимся обращаться с этими большими числами, мы сможем найти математические соотношения, которые помогут инженерам создавать большие сети коммуникаций, а учёным распознавать упорядоченные структуры в крупномасштабных физических системах. Сегодня мы с лёгкостью прослеживаем в созвездиях на ночном небосводе следствие теории Рамсея. А какие структуры можно найти в множествах, размеры которых в ACKERMANN(9) раз больше?

Рис.4. Понятия теории Рамсея приложимы к геометрическим задачам вроде этой головоломки о шестиугольниках. Если длины всех сторон шестиугольников равны 0,45 единицы (единица длины может быть произвольной), то две точки внутри шестиугольника отстоят друг от друга самое большее на 0,9 единицы. Каждый шестиугольник окрашивается одним из семи цветов, так, что никакие два шестиугольника одного цвета не отстоят друг от друга меньше чем на 1,19 единицы. Никакие две точки одного цвета не находятся одна от другой на расстоянии, в точности равном единице. Пока что никто не смог определить, можно ли раскрасить плоскость шестью красками так, чтобы никакие две точки одного цвета не находились в точности на расстоянии одной единицы друг от друга.

Список литературы

1. A.M.Gleason and R.E.Greenwood. Combinatorial Relations and Cromatic Graphs. In: Canadian Journal of Mathematics, 1955, v.7, No.1, pp.1–7.

2. B.L. van der Waerden. How the Proof of Baudet's Conjecture Was Found. In: Studies in Pure Mathematics (Edited by L.Mirsky). Academic Press, Inc., 1971.

3. Paul Erdös: The Art of Counting: Selected Writings (Edited by Joel Spencer). The MIT Press, 1973.

4. Paul Hoffman. The Man Who Loves Only Numbers. In: Atlantic Monthly, 1987, v.260, No.5, pp.60–74.

5. R.L.Graham and V.Rödl. Numbers in Ramsey Theory, in Surveys and in Combinatorics. London Mathematical Society Lecture Notes Series, 1987, No.123, pp.111–153.

6. Ronald L.Graham, Bruce L.Rothschild and Joel H.Spencer. Ramsey Theory. Second Edition. John Wiley & Sons, Inc., 1990.