Кого послать на Марс?

51

Кого после на Марс?

Кандидат физико-mатематических наук
М. В. ВОЛКОВ, Н. Н. СИЛКИН

Эта статья возвращает нас к теме, обсуждавшейся в статье М. Гарднера в четвертом номере «Кванта», — к «цветным графам» и теории Рамся. Эдесь расссказывает о нескольких типичных задачах этой теории и, в частности, приводится решение задачи M1099 (условие ее также было помещено в № 4, 1988), обсуждавются общее методы оценок в подобных задачах и их применения.

Основы механической дипломатии

Совершая очередное космическое путешествие, Громозека, космопроходец с огромным стажем, обнаружил незнакомую планетную систему. Он взял на нее курс и вскоре «приземился» на третью от центральной звезды пла-нету. Остотревшись, Громозека увидел неподалеку аборигана и направился к нему. Завязался ожиденный разговор, из которого Громозека узнал, что в Ух-ты (так, оказавется, называлась система) 9 планет, и все они обитаемые.

— Раньше,— сказал абориген Громозеке,— все наши планеты жили другно. Но после того, как здесь побывал Весельчак и Глот, некоторые планеты разорвали дипломатические отношения. Правда, среди любых четырех планет какие-то две по-прежнему другат между собой, но этого мало: ведь противостоять угрозащему нам вторжение сумчатых бегемотов могут только обединитьные силы трех планет!

— Прокляйте разбойники,— воскликнул Громозека.— Однако не все потеряно! В вашей системе есть три планеты, которые попарно другат между собой и, значит, могут обединиться!

53

рисунков, или, как их называют в математике, графов. Более точно, совокупность точек и соединяющих их линей называется графом, если 1) каждый линей соединяетрово две точки; 2) две любые точки соединены не более чем одной линей. При этом точки принято называть вершинами графа, а линей — ребрами графа. На рисунке 4 приведен один пример графа. Вершины $A, B, C, D$ на этом рисунке попарно соединены ребрами. Про также вершины говорят, что они образуют полный подграф. А вот среди вершин $E, F, G, H$ ни одна не соединена ребром с другой из тех же вершин. Такие вершины составляют пустой подграф.

Тепер задачу про шесть планет можно сформировать так: любой граф с шестю вершинами содержит любо полный подграф с трея вершинами, любо пустой подграф с трея вершинами. То, что Громозека доказал про планетную систему Ух-ты, по существу означает, что любой граф с девятью вершинами содержит любо полный подграф с трея вершинами, любо пустой подграф с четырьмя вершинами. Дальше естественно поинтересоваться: а какое минимальное число $p$ нужно взять, чтобы любой граф с $p$ вершинами содержал любо полный подграф с трея вершинами, любо пустой подграф с пятую вершинами. Но не будем торопиться ответить на него, ведь тогда появится следующий вопрос: какое минимальное число $q$ нужно взять, чтобы любой граф с $q$ вершинами содержал любо полный подграф с трея вершинами, любо пустой подграф с шестю вершинами, и т. д. Попробуем лучше обобщить нашу задачу, чтобы сразу ответить на все такие вопросы.

Итак, рассмотрим сразу общую ситуацию. Пусть $m$ и $n$ — натуральные числа, больше 1. Обозначим через $r(m, n)$ минимальное число с таким свойством, что любой граф не менее чем с $r(m, n)$ вершинами содержит любо полный подграф с тремя вершинами, любо пустой подграф с шестю вершинами, и т. д. Попробуем лучше обобщить нашу задачу, чтобы сразу ответить на все такие вопросы.

*) Требовательный читатель скажет: «Не ведь нет никакой гарантии, что такое число существует», и будет прав. Но из дальнейших рассуждений следует не только оценка числа $r(m, n)$, но и его существование.

54

Случай второй. Число вершин, связанных ребром с вершиной $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) \leqslant r(2, 3)+r(3, 2)=3+3=6$. Вот мы и доказали, что в любом графе с шестю вершинами найдется либо полный, либо пустой подграф с трея вершинами,— но теперь из общих соображений. Легко привести пример графа с пятую вершинами, в котором нет ни пустого, ни полного подграфа с трея вершинами (рис. 5). Поэтому число $r(3; 3)$ равно 6.

Что мы знаем и чего не знаем

Насколько точную оценку дает неравенство (1)? Попробуем-ка с его помощью получить утверждение Громозeki. Имеем:

$$r(3, 4) \leqslant r(2, 4)+r(3, 3)=4+6=10.$$

Осечка! Ведь Громозека доказал, что $r(3, 4) \leqslant 9!$ Оказывается, если она числа $r(m-1, n)$ и $r(m, n-1)$ четны, то справедливо неравенство

$$r(m, n) \leqslant r(m-1, n)+r(m, n-1)-1.$$

Доказывается оно так же, как и (1), нужно только учеть, что графа с $r(m-1, n)+r(m, n-1)-1$ вершинами, в котором каждая вершина соединенаровно с $r(m-1, n)-1$ вершинами, не существует.

Уражение 4. Доказите неравенство (2).

Заметим, что неравенству (2) можно придать такую удобную для использования форму: если $r(m-1, n) \leqslant A$ и $r(m, n-1) \leqslant B$, где $A$ и $B$ — четные числа, то $r(m, n) \leqslant A+B-1$.

Получая неравенством (2), утверждение Громозeki можно доказать в одну строку:

$$r(3, 4) \leqslant 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)$ до сих пор известно.)

Нетрудно заметить, что эта таблица симметрина относительно одной из диагоналей. Это не случайно: для всех $m$ и $n$ верна формула $r(m, n)=r(n, m)$.

Уражение 5. Доказите эту формулу.

Теперь мы готовы начать

Решение задачи M1099

В отряде, ведущем подготовку к получению Марс, 6783 космонавта, при-

55

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

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

Пусть $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) \leq r(R(m-1, n), R(m, n-1)) + 1. \quad (3)$$

Его доказательство похож на доказательство неравенства (1). Нам нужно доказать, что в любом отряде из $r(R(m-1, n), R(m, n-1)) + 1$ космонавтов найдет либо $m$ целое, среди которых либо является сложной, либо $n$ целое, никакие

56

$$R(5, 4) \leq r(R(4, 4), R(5, 3)) + 1.$$
Число $R(5, 3)$ равно 5, а чтобы оценить $R(4, 4)$, снова применим (3):
$$R(4, 4) \leq r(R(3, 4), R(4, 3)) + 1 = r(4, 4) + 1.$$
Число $r(4, 4)$ можно оценить, используя (1). Получим
$$r(4, 4) \leq r(3, 4) + r(4, 3) = 9 + 9 = 18.$$
(На самом деле, как видно из таблицы, 18 — это точное значение числа $r(4, 4)$.) Итак, $R(4, 4) \leq 19$, и $R(5, 4) \leq r(19, 5) + 1$. Остается оценить число $r(19, 5)$. Это можно сделать, многократно применяя неравенства (1) и (2):
$$r(5, 3) \leq r(4, 3) + r(5, 2) = 9 + 5 = 14,$$
$$r(6, 3) \leq 14 + 6 - 1 = 19,$$
$$r(7, 3) \leq 19 + 7 = 26,$$
$$r(8, 3) \leq 26 + 8 - 1 = 33,$$
и т. д., до $r(19, 3)$; получится $r(19, 3) \leq 182$.
Затем пишем:
$$r(4, 4) \leq r(3, 4) + r(4, 3) = 9 + 9 = 18,$$
$$r(5, 4) \leq 18 + 14 - 1 = 31,$$
$$r(6, 4) \leq 31 + 19 = 50,$$
… …
$$r(19, 4) \leq 1249;$$
$$r(5, 5) \leq r(4, 5) + r(5, 4) = 31 + 31 = 62,$$
$$r(6, 5) \leq 62 + 50 - 1 = 111,$$
… …
$$r(19, 5) \leq 6782.$$
Следовательно, $R(5, 4) \leq 6783$.
Оценка $R(5, 4) \leq 6783$ не является точной. Если воспользоваться значениями чисел $r(m, n)$ из ранее приведенной таблицы, то, рассуждая в полне аналогично, можно получить существенное лучшую оценку: $R(5, 4) \leq 6337$. Авторы умел доказать, что $R(5, 4) \leq 6242$, но будет ли точной эта оценка, им неизвестно.

Teorema Рамсея

Начав с простых сообщений, мы обнаружили, что они являются следствиями некоторых общих закономерностей: неравенств (1) и (3). Эти закономерности позволили нам решить задачу M1099. Но оказались, что и сами они — всего лишь частиные случаи еще более общого результата, полученного в 1930 году английским логиком Ф. Рамсеем (1903—1930). Для того чтобы сформировать теорему Рамсея, представим, что в полет к Марсу нужно отправить не 5, а $m$ человек, из которых не 3, а $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≥s и n≥s. Ето можно оценить с помощью неравенства

$$R(s; m, n) \leq R(s - 1);$$
$$R(s; m - 1, n), R(s; m, n - 1)) + 1.$$

Неравенство (4) очень похож на неравенство (3). Оно и доказывает, по существу, точно так же. Нужно только рассматривать не пары космосов, а экппаж из $s-1$ космосов. Ясно, что неравенства (1) и (3) — частиные случаи неравенства (4) при $s=2$ (нужно учеть упражнение 7) и $s=3$ соответствующего. Теорема Рамсея имеет очень много приложений в самых различных областях математики: в математической логике и в теории чисел, в алгебре и в combinatorике, в геометрии и даже в программировании. Эти приложения заключают отдельного разговора, а здесь, в качестве примера того, как применяется теорема Рамсея, приведем только один изящный результат, который принадлежит в генерации математики П. Эрдёшу и Д. Секерешу.

Teorema Эрдёша — Секереша. Для любого натурального числа