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

Талантливыйматематик Фрэнк Пламптон Рамсей доказал, что полная неупорядоченностьневозможна. Каждое достаточно большое множество чисел, точек или объектовобязательно содержит высоко упорядоченную структуру
Рональд Л. Грэм, Джоуэл X. Спенсер
Какповествует написанный три с половиной тысячи лет назад клинописный текст,однажды древнешумерский учёный взглянул на звёздное небо и увидел льва, буйволаи скорпиона. Современный астроном скорее всего склонен описывать созвездие каквременную группу звёзд, которую мы, земляне, наблюдаем с одной точки на краюобычной галактики. И всё же большинство любителей поглазеть на звёздысогласятся, что ночное небо выглядит сплошь усыпанным созвездиями, имеющимиформу прямых линий, четырёхугольников и пятиугольников. Может ли так быть, чтоподобные геометрические фигуры порождаются какими-то неизвестными нам силами,действующими во Вселенной?
Математикапредлагает куда более простое объяснение. В 1928году Фрэнк Пламптон Рамсей,английский математик, философ и экономист, доказал, что такие упорядоченныеконфигурации неизбежно присутствуют в любой большой структуре, будь то группазвёзд, совокупность случайно разбросанных камешков или последовательностьчисел, полученных бросанием игральной кости. Если речь идёт о достаточнобольшом количестве звёзд, то всегда можно найти группу, которая с очень большойточностью образует какую-нибудь заданную конфигурацию: прямую линию,прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактическитеория Рамсея утверждает, что любая структура обязательно содержитупорядоченную подструктуру. Как впервые провозгласил около четверти века назадумерший недавно американский математик Теодор С.Моцкин, из теории Рамсея следует,что полный беспорядок невозможен.
Специалистыпо теории Рамсея стараются вычислить, сколь велико должно быть множество звёзд,чисел или каких-либо объектов, чтобы можно было гарантировать существованиеопределённой желаемой подструктуры. На решение таких задач часто требуютсядесятилетия, и поддаются они только при самом изобретательном и тонкомрассуждении. Пытаясь найти решения поставленной задачи, специалисты по теорииРамсея помогают тем самым инженерам в построении более совершенных сетей коммуникациии систем передачи и поиска информации. Они также открыли некоторыематематические методы, которые пригодятся учёным следующего столетия. Возможно,самое важное заключается в том, что теория Рамсея исследует основополагающуюструктуру математики, т.е. структуру, пронизывающую всю Вселенную.
Вотличие от многих разделов современной математики теорию Рамсея можно изложитьна интуитивном уровне. В самом деле, привлекательность этой теории отчастиобусловлена той простотой, с которой можно сформулировать её задачи. Например,если из присутствующих на вечеринке случайным образом выбрать шесть человек(скажем, Альфреда, Бетти, Кэлвина, Дебору, Эдварда и Фрэнсис), то верно ли, чтолибо трое из них друг с другом знакомы, либо трое из них незнакомы друг с другом?
Мыможем решить эту «головоломку о вечеринке» многими способами. Мы могли быперебрать все мыслимые комбинации и проверить, содержит ли каждаярассматриваемая группа трёх знакомых или трёх незнакомых людей. Но посколькунам пришлось бы проверить 32768 (или 215) комбинаций, то такой«метод грубой силы» не является ни практичным, ни поучительным.
Ксчастью, мы можем отыскать ответ, рассмотрев два простых случая. В первом изних предположим, что Альфред знает трёх (или больше) из числа остальных гостей,скажем, Бетти, Кэлвина и Дебору. Если Бетти и Кэлвин, или Бетти и Дебора, илиКэлвин и Дебора знакомы друг с другом, то Альфред и пара знакомых образуютгруппу из трёх знакомых людей; в противном случае Бетти, Кэлвин и Дебора друг сдругом незнакомы. Во втором случае предположим, что Альфред знает самое большеедвух (или меньше) из гостей, скажем, Бетти и Кэлвина. Если Дебора и Эдвард, илиДебора и Фрэнсис, или Эдвард и Фрэнсис незнакомы друг с другом, то Альфред ипара незнакомых между собой гостей образуют группу из трёх человек, незнакомыхдруг с другом. В противном случае Дебора, Эдвард и Фрэнсис друг с другомзнакомы. Всего в шести предложениях мы доказали, почему любая группа из шестичеловек должна включать или трёх знакомых, или трёх незнакомых людей. Корочеговоря, решение «головоломки о вечеринке» есть частный случай теории Рамсея.
/> Рис.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+2k–2, где k=3, 4, 5… и т.д.,то можно ли всегда выбрать k точек, образующих выпуклый многоугольник?
Всвоих воспоминаниях Шекереш так описывает последующие события: «Мы вскореосознали, что простые рассуждения не подходят, и появилось волнующее чувство,что в нашем кружке впервые возник новый тип геометрических задач». Шекерешпоказал, что существует такое число n, что если n точек лежат на плоскости так,что никакие три из них не находятся на одной прямой, то среди них всегда можнонайти k точек, образующих выпуклый k-угольник. Другими словами, если точекдостаточно много, всегда можно найти их подмножество, образующее многоугольникс заданным числом сторон. Доказав это, Шекереш заново открыл теорему Рамсея,хотя никто из их группы в то время не знал о ней.
В1934году Эрдёш и Шекереш опубликовали свои результаты, хотя ни они, ни кто-либодругой до сих пор не смогли доказать гипотезу Эрдёша о том, что числа точек n=1+2k–2достаточно. Эрдёш часто называет эту совместную публикацию «статьёй сосчастливым концом», поскольку вскоре после её опубликования Шекереш и Клейнпоженились. Эрдёш же стал самым продуктивным математиком нашего столетия.
Эрдёшзаинтересовался идеей Рамсея о том, что всякая достаточно большая структурадолжна содержать регулярную подструктуру заданного размера. Но ему хотелосьузнать, какого именно размера должна быть эта структура, чтобы существованиеопределённой подструктуры было гарантировано. Так Эрдёш начал работать надвариантом головоломки о вечеринке.
Вэтом варианте шесть человек представлены шестью точками. Для удобства точкирасполагаются на плоскости так, чтобы никакие три из них не лежали на однойпрямой. Точки соединяются ребром, которое окрашивается, чтобы представитьотношения между соответствующими двумя людьми. Красное ребро означает, что этилюди между собой знакомы, а синее ребро — что они друг друга не знают.
Следовательно,если три человека знакомы друг с другом, то рёбра между соответствующимиточками образуют красный треугольник, а если эти трое незнакомы, то образуетсясиний треугольник. Головоломку о вечеринке тогда можно сформулировать так:верно ли, что если каждое ребро, соединяющее любые две из шести точек, окраситьв синий или красный цвет произвольным образом, то всегда возникает либо синий,либо красный треугольник?
Задача,которую изучал Эрдёш, представляет собой обобщение этой задачи. Он определилполную сеть как набор точек, каждая из которых соединена рёбрами со всемиостальными. Затем он задался вопросом: какова наименьшая полная сеть, котораябудучи произвольным образом раскрашена в красный и синий цвет, обязательносодержит полную сеть красного или синего цвета? Ответ следующий: полная сеть —из шести точек. Эту задачу и её решение удобнее выразить так: число Рамсея (R)для трёх красных и трёх синих равно шести.
Акак насчет числа Рамсея для пяти красных и трёх синих? Другими словами, какованаименьшая полная сеть, которая будучи произвольным образом раскрашена вкрасный и синий цвет, обязательно содержала бы либо красную сеть из пяти точек,либо синюю сеть из трёх точек? Число Рамсея для пяти красных и трёх синих равно14, что доказали только в 1955году Роберт Гринвуд из Университета шт.Техас вОстине и Эндрю Глисон из Гарвардского университета.
/>
/>
/> 5 />
/> 17 />
/> 27 ЧислаРамсея чрезвычайно трудно вычислять. Усилиями поколений математиков икомпьютеров удалось найти лишь семь чисел Рамсея, которые приведены на рис.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×10165×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 всеголишь пять раз даёт 265536, — число, которое, будучи записанным цифраза цифрой, заполнило бы две страницы этого журнала. На самом деле даже число,заполняющее все страницы всех книг и всю память всех компьютеров, всё жеостанется несравнимым с 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 ofMathematics, 1955, v.7, No.1, pp.1–7.
2. B.L. van der Waerden. How the Proof ofBaudet's Conjecture Was Found. In: Studies in Pure Mathematics (Edited byL.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 OnlyNumbers. In: Atlantic Monthly, 1987, v.260, No.5, pp.60–74.
5. R.L.Graham and V.Rödl. Numbers inRamsey Theory, in Surveys and in Combinatorics. London Mathematical SocietyLecture Notes Series, 1987, No.123, pp.111–153.
6. Ronald L.Graham, Bruce L.Rothschild andJoel H.Spencer. Ramsey Theory. Second Edition. John Wiley & Sons, Inc.,1990.