Текст статьиВолков М. В., Силкин Н. Н. Кого послать на Марс? // Квант. — 1988. — № 8. — С. 51—57.
Эта статья возвращает нас к теме, обсуждавшейся в статье М. Гарднера в четвёртом номере «Кванта», — к «цветным графам» и теории Рамсея. Здесь рассказывается о нескольких типичных задачах этой теории и, в частности, приводится решение задачи М1099 (условие её также было помещено в №4, 1988), обсуждаются общие методы оценок в подобных задачах и их применения.
Основы межпланетной дипломатии
Совершая очередное космическое путешествие, Громозека, космопроходец с огромным стажем, обнаружил незнакомую планетную систему. Он взял на неё курс и вскоре «приземлился» на третью от центральной звезды планету. Осмотревшись, Громозека увидел неподалёку аборигена и направился к нему. Завязался оживлённый разговор, из которого Громозека узнал, что в Ух-ты (так, оказывается, называлась система) 9 планет, и все они обитаемы.
— Раньше, — сказал абориген Громозеке, — все наши планеты жили дружно. Но после того, как здесь побывали Весельчак и Глот, некоторые планеты разорвали дипломатические отношения. Правда, среди любых четырёх планет какие-то две по-прежнему дружат между собой, но этого мало: ведь противостоять угрожающему нам вторжению сумчатых бегемотов могут только объединённые силы трёх планет!
— Проклятые разбойники, — воскликнул Громозека. — Однако не всё потеряно! В вашей системе есть три планеты, которые попарно дружат между собой и, значит, могут объединиться!
В ответ на недоумённый взгляд аборигена Громозека вывернул из грунта 9 камней.
— Представьте себе, что это девять планет системы Ух-ты, — начал Громозека. — Как называется ваша планета?
— Зям-лям, — ответил абориген.
— А теперь представьте, что этот камень — Зям-лям, — с этими словами Громозека поставил аборигена на один из камней. — Теперь я буду coединять сплошной линией две планеты тогда и только тогда, когда они дружат, а рассорившиеся планеты буду соединять пунктиром. Пусть нашлись 4 планеты, с которыми дружит Зям-лям; тогда среди них обязательно есть две, которые дружат между собой.
Громозека провёл соответствующие линии между камнями (рис. 1) и продолжал:
— Получился треугольник. Это и есть тройка дружных планет! Пусть теперь Зям-лям состоит в дипломатических отношениях не более чем с двумя планетами. Тогда по крайней мере с шестью она находится в ссоре (рис. 2). Среди этих шести планет всегда есть либо три попарно дружные между собой планеты, либо три попарно поссорившиеся. Это-то вам ясно?
— Ясно, — согласился абориген. (Он вспомнил, что встречал подобную теорему в одном научно-популярном журнале. Читателю же мы предлагаем доказать этот факт в качестве упражнения 1.)
— Отлично! Но трёх попарно поссорившихся планет среди шести, порвавших отношения с Зям-лямом, быть не может: иначе получится, что есть четыре попарно поссорившиеся планеты (рис. 3). Вот и всё, — закончил свои объяснения Громозека.
— Нет, не всё, — возразил абориген, слезая с камня, — а если Зям-лям в ссоре ровно с пятью планетами, а дружит ровно с тремя?
— Тогда те же рассуждения можно применить к какой-нибудь другой планете, у которой больше друзей или больше недругов, — пояснил Громозека.
— А если каждая из планет в ссоре с пятью, а дружит ровно с тремя? — не унимался абориген.
— Мой друг, не волнуйтесь, — успокоил его Громозека, — систем из девяти планет, каждая из которых дружит ровно с тремя, не может быть ни в одной галактике. Поверьте моему богатому опыту космопроходца!
Упражнение 2. Проверьте и это утверждение Громозеки.
Надеемся, что читатель сможет выполнить упражнения 1 и 2, не прибегая к межгалактическим путешествиям. А мы пока, «установив исходные факты, начнём строить, основываясь на них, нашу теорию...» (А. Конан Дойл, «Серебряный» ).
Некоторые выводы
Громозека иллюстрировал свои рассуждения рисунками из точек и линий, и это не случайно. Утверждения, которые он доказал, удобнее всего формулировать с помощью именно таких рисунков, или, как их называют в математике, графов. Более точно, совокупность точек и соединяющих их линий называется графом, если
каждая линия соединяет ровно две точки;
две любые точки соединены не более чем одной линией.
При этом точки принято называть вершинами графа, а линии — рёбрами графа. На рисунке 4 приведён один пример графа. Вершины $A$, $B$, $C$, $D$ на этом рисунке попарно соединены рёбрами. Про такие вершины говорят, что они образуют полный подграф. А вот среди вершин $E$, $F$, $G$, $H$ ни одна не соединена ребром с другой из тех же вершин. Такие вершины составляют пустой подграф.
Теперь задачу про шесть планет можно сформулировать так: любой граф с шестью вершинами содержит либо полный подграф с тремя вершинами, либо пустой подграф с тремя вершинами. То, что Громозека доказал про планетную систему Ух-ты, по существу означает, что любой граф с девятью вершинами содержит либо полный подграф с тремя вершинами, либо пустой подграф с четырьмя вершинами. Дальше естественно поинтересоваться: а какое минимальное число $p$ нужно взять, чтобы любой граф с $p$ вершинами содержал либо полный подграф с тремя вершинами, либо пустой подграф с пятью вершинами. Но не будем торопиться отвечать на него, ведь тогда появится следующий вопрос: какое минимальное число $q$ нужно взять, чтобы любой граф с $q$ вершинами содержал либо полный подграф с тремя вершинами, либо пустой подграф с шестью вершинами, и т. д. Попробуем лучше обобщить нашу задачу, чтобы сразу ответить на все такие вопросы.
Итак, рассмотрим сразу общую ситуацию. Пусть $m$ и $n$ — натуральные числа, большие 1. Обозначим через $r(m,n)$ минимальное число с таким свойством, что любой граф не менее чем с $r(m,n)$ вершинами содержит либо полный подграф с $m$ вершинами, либо пустой подграф с $n$ вершинами. (Читатель, знакомый с упоминавшейся статьёй Гарднера, узнает в числах $r(m,n)$ числа Рамсея.) Наша задача — найти число $r(m,n)$. Это нетрудно сделать, если $n=2$: тогда $r(m,2)=m$. В самом деле, в любом графе с $m$ вершинами либо все вершины попарно соединены рёбрами, либо найдутся две вершины, не связанные ребром между собой. В первом случае в графе есть полный подграф с $m$ вершинами (совпадающий со всем графом), а во втором случае в графе есть пустой подграф с двумя вершинами. Так же легко доказать, что $r(2,n)=n$ при любом $n$.
Упражнение 3. Докажите эту формулу.
Хотелось бы и при других $m$ и $n$ найти простую формулу для числа $r(m,n)$. Увы, пока такая формула неизвестна. Но несложно доказать следующее неравенство, позволяющее оценивать число $r(m,n)$, если известны числа $r(m-1,n)$ и $r(m,n-1)$:
$$
r(m,n)\le r(m-1,n)+r(m,n-1).\tag1
$$
Для этого нужно только проверить, что в любом графе с $r(m-1,n)+r(m,n-1)$ вершинами есть либо полный подграф с $m$ вершинами, либо пустой подграф с $n$ вершинами. Возьмём в таком графе одну из вершин, обозначим её через $X$ и рассмотрим два случая.
Случай первый. Число вершин, связанных рёбрами с вершиной $X$, не меньше чем $r(m-1,n)$. Тогда среди этих вершин либо $m-1$ вершин составляют полный подграф (и вместе с $X$ получается полный подграф с $m$ вершинами), либо $n$ вершин образуют пустой подграф.
Случай второй. Число вершин, связанных ребром с вершиной $X$, меньше чем $r(m-1,n)$. Но тогда по крайней мере $r(m,n-1)$ вершин не соединены с $X$. Среди этих вершин либо $m$ вершин составляют полный подграф, либо $n-1$ вершин образуют пустой подграф (и вместе с вершиной $X$ получается пустой подграф с $n$ вершинами).
Посмотрим, как применяется неравенство (1). Вычислим, к примеру, число $r(3;3)$. Из формул $r(2,n)=n$ и $r(m,2)=m$ и из неравенства (1) получаем, что $r(3,3)\le r(2,3)+r(3,2)=3+3=6$. Вот мы и доказали, что в любом графе с шестью вершинами найдётся либо полный, либо пустой подграф с тремя вершинами, — но теперь из общих соображений. Легко привести пример графа с пятью вершинами, в котором нет ни пустого, ни полного подграфа с тремя вершинами (рис. 5). Поэтому число $r(3;3)$ равно 6.
Что мы знаем и чего не знаем
Насколько точную оценку даёт неравенство (1)? Попробуем-ка с его помощью получить утверждение Громозеки. Имеем:
$$
r(3,4)\le r(2,4)+r(3,3)=4+6=10
$$
Осечка! Ведь Громозека доказал, что $r(3,4)\le9$! Оказывается, если оба числа $r(m-1,n)$ и $r(m,n-1)$ чётны, то справедливо неравенство
$$
r(m,n)\le r(m-1,n)+r(m,n-1)-1.\tag2
$$
Доказывается оно так же, как и (1), нужно только учесть, что графа с $r(m-1,n)+r(m,n-1)-1$ вершинами, в котором каждая вершина соединена ровно с $r(m-1,n)-1$ вершинами, не существует.
Упражнение 4. Докажите неравенство (2).
Заметим, что неравенству (2) можно придать такую удобную для использования форму: если $r(m-1,n)\le A$ и $r(m,n-1)\le B$, где $A$ и $B$ — чётные числа, то $r(m,n)\le A+B-1$.
Пользуясь неравенством (2), утверждение Громозеки можно доказать в одну строчку:
$$
r(3,4)\le r(2,4)+r(3,3)-1=4+6-1=9.
$$
На рисунке 6 изображён граф с восьмью вершинами, в котором нет ни полного подграфа с тремя вершинами, ни пустого подграфа с четырьмя вершинами. Поэтому число $r(3,4)$ равно $9$.
Мы уже отмечали, что при $m$ и $n$, больших 2, точная формула для числа $r(m,n)$ неизвестна. Более того, точное значение этого числа известно пока только для некоторых небольших $m$ и $n$.
Мы приводим таблицу, в которой собраны, пожалуй, все известные на сегодня сведения о значениях $r(m,n)$. (Значение $r(9,3)=36=r(3,9)$ найдено совсем недавно с помощью ЭВМ. А вот точное значение числа $r(3,8)$ до сих пор неизвестно.)
$$
\def\a#1{\mathclap{#1}}
\def\b#1{\a{\hphantom{00}\mathllap{#1}}}
\def\A{\colsep{0pt}{\begin{array}{lr}\diagdown&m\\[-3pt]n&\diagdown\end{array}}}
\def\|{\vphantom{\dfrac00}}
\colsep{1em}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\mathclap{\A}&\a3&\a4&\a5&\a6&\a7&\a8&\a9\|\\\hline\\[-6pt]
\a3&\b6&\b9&\b{14}&\b{18}&\b{23}&&\b{36}\\
\a4&\b9&\b{18}&&&&&\\
\a5&\b{14}&&&&&&\\
\a6&\b{18}&&&&&&\\
\a7&\b{23}&&&&&&\\
\a8&&&&&&&\\
\a9&\b{36}&&&&&&\\[6pt]\hline
\end{array}}
$$
Нетрудно заметить, что эта таблица симметрична относительно одной из диагоналей. Это не случайно: для всех $m$ и $n$ верна формула $r(m,n)=r(n,m)$.
Упражнение 5. Докажите эту формулу.
Теперь мы готовы начать
Решение задачи М1099
В отряде, ведущем подготовку к полёту на Марс, 6783 космонавта, причём известно, что среди любых четырёх из них можно выбрать троих, составляющих слаженный экипаж Оля посадочного модуля. Докажите, что можно выбрать 5 космонавтов, любые трое из которых составляют слаженный экипаж.
Вероятно, читатель уже убедился в полезности обобщений. Давайте и сейчас отвлечёмся от конкретных данных задачи М1099 и рассмотрим её «в общем виде».
Пусть $m$ и $n$ — натуральные числа, большие 2. Обозначим через $R(m,n)$ минимальное число с тем свойством, что в любом отряде из $R(m,n)$ космонавтов можно выбрать либо $m$ человек, любые 3 из которых образуют слаженный экипаж, либо $n$ человек, никакие 3 из которых не образуют слаженный экипаж. Читатель, возможно, ожидает, что мы переформулируем эту задачу на языке графов и извлечём нужную информацию из предыдущих результатов. Но он будет на этот раз неправ. Числа $R(m,n)$ непосредственно не связаны с графами, хотя и имеют некоторое отношение к числам $r(m,n)$.
Прежде всего, можно понять, что для всех $m$ и $n$ верны равенства:
$$
R(3,n)=n,\quad R(m,3)=m,\quad R(m,n)=R(n,m),
$$
похожие на отмечавшиеся выше равенства для чисел $r(m,n)$.
Упражнение 6. Обоснуйте эти равенства.
Раз между числами $R(m,n)$ и $r(m, n)$ существует сходство, можно ожидать, что числа $R(m,n)$ можно оценивать с помощью чисел $R(m-1,n)$ и $R(m,n-1)$ аналогично тому, как мы оценивали числа $r(m,n)$, пользуясь неравенством (1). И в самом деле, верно неравенство
$$
R(m,n)\le r(R(m-1,n),R(m,n-1))+1.\tag3
$$
Его доказательство похоже на доказательство неравенства (1). Нам нужно доказать, что в любом отряде из $r(R(m-1,n),R(m,n-1))+1$ космонавтов найдутся либо $m$ человек, среди которых любая тройка является слаженной, либо $n$ человек, никакие трое из которых не могут составить слаженный экипаж. Выделим теперь одного космонавта — $X$. Каждому из оставшихся космонавтов сопоставим одну точку и соединим линией такие пары точек, что соответствующие пары космонавтов образуют вместе с космонавтом $X$ слаженный экипаж. В полученном графе с $r(R(m-1,n),R(m,n-1))$ вершинами найдётся либо полный подграф с $R(m-1,n)$ вершинами, либо пустой подграф с $R(m,n-1)$ вершинами (это следует из определения числа $r(R(m-1, n),R(m, n-1))$).
Рассмотрим первый случай: в отряде космонавтов есть $R(m-1,n)$ человек, любые двое из которых образуют вместе с $X$ слаженный экипаж. По определению числа $R(m-1,n)$ среди них найдутся либо $m-1$ человек, любые трое из которых образуют слаженный экипаж (и вместе с космонавтом $X$ получится $m$ таких человек), либо $n$ человек, никакие трое из которых не могут составить слаженный экипаж.
Во втором случае в отряде есть $R(m,n-1)$ человек, никакие двое из которых не могут образовать вместе с космонавтом $X$ слаженный экипаж. В свою очередь, среди них найдутся либо $m$ человек, любая тройкa из которых слаженная, либо $n-1$ человек, никакие трое из которых не в состоянии образовать слаженный экипаж (и вместе с космонавтом $X$ получится $n$ таких человек).
Неравенство (3) доказано, причём попутно мы доказали и факт существования чисел $R(m,n)$ для всех $m$ и $n$ (заранее далеко неочевидный).
Теперь для того, чтобы решить задачу М1099, достаточно проверить, что число $R(5,4)$ меньше, чем 6783. Ведь тогда в любом отряде из 6783 космонавтов найдётся либо 5 космонавтов, любая тройка из которых — слаженная, либо 4 космонавта, никакие три из которых не годятся для высадки на Марс. Второй случай по условию задачи невозможен, и остаётся только первая возможность.
Итак, займёмся оценкой числа $R(5,4)$. Применяя (3), получим
$$
R(5,4)\le r(R(4,4),R(5,3))+1.
$$
Число $R(5,3)$ равно 5, а чтобы оценить $R(4,4)$, снова применим (3):
$$
R(4,4)\le r(R(3,4),R(4, 3))+1=r(4,4)+1.
$$
Число $r(4,4)$ можно оценить, используя (1). Получим
$$
r(4,4)\le r(3,4)+r(4,3)=9+9=18.
$$
(На самом деле, как видно из таблицы, 18 — это точное значение числа $r(4,4)$.) Итак, $R(4,4)\le19$, и $R(5,4)\le r(19,5)+1$. Остаётся оценить число $r(19,5)$. Это можно сделать, многократно применяя неравенства (1) и (2):
$$
\begin{aligned}
r(5,3)&\le r(4,3)+r(5,2)=9+5=14,\\
r(6,3)&\le 14+6-1=19,\\
r(7,3)&\le 19+7=26,\\
r(8,3)&\le 26+8-1=33,
\end{aligned}
$$
и т. д., до $r(19,3)$; получится $r(19,3)\le182$.
Оценка $R(5,4)\le6783$ не является точной. Если воспользоваться значениями чисел $r(m,n)$ из ранее приведённой таблицы, то, рассуждая вполне аналогично, можно получить существенно лучшую оценку: $R(5,4)\le6337$. Авторы умеют доказывать, что $R(5,4)\le6242$, но будет ли точной эта оценка, им неизвестно.
Теорема Рамсея
Начав с простых соображений, мы обнаружили, что они являются следствиями некоторых общих закономерностей: неравенств (1) и (3). Эти закономерности позволили нам решить задачу М1099. Но оказывается, что и сами они — всего лишь частные случаи ещё более общего результата, полученного в 1930 году английским логиком Ф. Рамсеем (1903—1930). Для того чтобы сформулировать теорему Рамсея, представим, что в полёт к Марсу нужно отправить не 5, а $m$ человек, из которых не 3, а $s$ должны высадиться на планету. Пусть известно, что из любых $n$ космонавтов ($n\ge s$), ведущих подготовку к полёту, можно выбрать $s$, которые составляют слаженный экипаж для посадочного модуля. Обозначим через $R(s;m,n)$ минимальное число космонавтов, среди которых можно выбрать $m$ таких человек, что любые $s$ из них образуют слаженный экипаж. Ясно, что при $s=3$ число $R(s;m,n)$ совпадает с числом $R(m,n)$; нетрудно также сообразить, что при $s=2$ это число равняется числу $r(m,n)$.
Упражнение 7. Проверьте, что $R(1;m,n)=m+n-1$.
Поставим теперь вопрос: при любом ли $s$ существует число $R(s;m,n)$? И если существует, то как его находить? На эти вопросы отвечает
Теорема Рамсея.Число $R(s;m,n)$ существует при любом $s$ и при любых $m\ge s$ и $n\ge s$. Его можно оценить с помощью неравенства
$$
R(s;m,n)\le R(s-1;R(s;m-1,n),R(s;m,n-1))+1.\tag4
$$
Неравенство (4) очень похоже на неравенство (3). Оно и доказывается, по существу, точно так же. Нужно только рассматривать не пары космонавтов, а экипажи из $s-1$ космонавтов. Ясно, что неравенства (1) и (3) — частные случаи неравенства (4) при $s=2$ (нужно учесть упражнение 7) и $s=3$ соответственно. Теорема Рамсея имеет очень много приложений в самых различных областях математики: в математической логике и в теории чисел, в алгебре и в комбинаторике, в геометрии и даже в программировании. Эти приложения заслуживают отдельного разговора, а здесь, в качестве примера того, как применяется теорема Рамсея, приведём только один изящный результат, который принадлежит венгерским математикам П. Эрдёшу и Д. Секерешу.
Теорема Эрдёша—Секереша.Для любого натурального числа $m\ge3$ существует наименьшее натуральное число $C(m)$ такое, что среди любых $C(m)$ точек плоскости, из которых никакие три не лежат на одной прямой, можно найти $m$ точек, являющихся вершинами выпуклого $m$-угольника.
Упражнение 8. Докажите теорему Эрдёша—Секереша.
Задачи
На планете Зям-лям 17 государств. Некоторые из них дружат между собой, некоторые враждуют, а некоторые нейтральны по отношению друг к другу. Докажите, что на Зям-ляме есть либо тройка попарно дружественных, либо тройка попарно враждебных, либо тройка попарно нейтральных государств.
На плоскости нарисованы 19 кругов так, что среди любых четырёх кругов какие-то три имеют общую точку. Докажите, что найдутся четыре круга, имеющие общую точку.
Натуральные числа от 1 до 66 покрашены в четыре цвета. Докажите, что среди них найдутся три числа $x$, $z$, $z$ одного цвета такие, что $x+y=z$.
