Математика имеет каверзное свойство очень быстро все усложнять и запутывать. Казалось бы, начали вы разбирать простую и всем понятную задачку, и вот — оглянуться не успели, как все вышло из-под контроля, а у вас от напряжения мозг свело.
Рассмотрим одну из таких задачек. На обеде, куда приглашены шестеро гостей, либо трое из них уже знакомы друг с другом, либо трое совершенно друг друга не знают. Докажите это.
Ситуация вполне правдоподобная, но, сколько ни думай, доказательство все время ускользает. В условии не говорится, что собравшиеся делятся на две группы: друзья и незнакомцы. Также нигде не сказано, что они все не могут быть друзьями или чужаками. Вроде бы очевидно: если среди собравшихся есть двое друзей, то остальные четверо должны быть чужаками, но это тоже неверно. Двое из этих самых «чужаков» могут быть знакомы между собой, но не знать ни одного из «друзей».
А вот математик враз покончит со всей этой неразберихой. Он возьмет карандаш, а лучше два карандаша, красный и синий, или даже три — красный, синий и черный, и нарисует круг из шести черных точек, каждая из которых обозначает гостя. Затем он соединит красными линиями все пары людей, которые знают друг друга, и синими линиями — пары незнакомцев. В этом узоре из пятнадцати линий обязательно окажется либо красный, либо синий треугольник: трое людей, знакомых друг с другом, либо трое, которые друг друга не знают.
Конечно, рисунок не доказывает изначальное высказывание, зато он переводит неясную ситуацию с людьми в четкое математическое выражение. Задача теперь рассматривает точки, соединенные линиями, то есть схему, а не людей и их взаимоотношения.
Область математики, имеющая дело с такими задачами, называется теорией Рамсея — в честь гениального кембриджского математика Фрэнка Пламптона Рамсея (1903–1930), умершего в 26-летнем возрасте, но успевшего внести существенный вклад в математику, экономику и философию. Задачка с обедом — одна из простейших в этой области, графы к более сложным задачам содержат больше точек, соединенных большим количеством линий. Граф, в котором каждая точка соединена со всеми остальными точками прямыми линиями, называется «полный граф». Граф, находящийся внутри этого множества линий, например красный или синий треугольник из вышеописанного примера, носит название «подграфа». Задачи в теории Рамсея обычно формулируются в виде вопросов типа: каково должно быть минимальное количество точек, чтобы образованный ими полный граф, случайным образом нарисованный красным или синим карандашами, содержал либо красный треугольник, либо синий четырехугольник?
Такие задачи на удивление трудно поддаются решению. Если в задачке про обед изменить условие и вместо трех сделать пятерых друзей или пятерых незнакомцев, то решить ее станет невозможно. Ответ можно будет выразить как R (5,5) — минимальное число гостей, необходимое, чтобы среди них оказалось либо пятеро друзей, либо пятеро человек, незнакомых друг с другом, но что это за число — никто не знает. Максимально близко к ответу ученые подошли, когда определили, что это R (5,5) находится где-то между 43 и 49. Венгерский математик Пал Эрдёш (1913–1996) однажды написал: «Представим себе, что некая инопланетная армия, куда более могущественная, чем наша, прилетит на Землю и потребует сообщить им точное значение R (5,5), а в противном случае пригрозит уничтожить нашу планету. Чтобы найти это значение, нам потребуется привлечь все имеющиеся компьютеры и математиков. А случись инопланетянам, допустим, потребовать значение R (6,6) — проще будет сразу попытаться уничтожить пришельцев».
Хотя считается, что математиков во всем интересует точность, иногда они согласны и на меньшее. Знать, что значение R (5,5) лежит между 43 и 39, почти так же хорошо, как, скажем, установить, что оно равняется 46. (Если вдруг впоследствии окажется, что это правильный ответ, обязательно потребую признать себя автором великого открытия!) Но в одной конкретной рамсеевской задаче эта терпимость к неточностям приводит к смехотворным результатам.
Наряду с подграфами, которые содержатся в полных графах, нарисованных на плоскости (как в вышеописанных примерах), теория Рамсея может задаваться вопросами касательно подграфов, находящихся в трехмерных полных графах. Например, нарисуйте восемь точек на плоскостях близ угла куба и соедините их все между собой — вы получите множество линий, среди которых будут попадаться разнообразные более простые фигуры. Теперь можно задавать вопросы касательно отдельных подграфов в этом полном графе, включая те, что лежат на плоскости. Все треугольники, разумеется, окажутся на плоскости, но подграфы из четырех и более точек — необязательно.
Для математиков, занимающихся теорией Рамсея, двух- и трехмерные фигуры — детский сад. Рамсеевская задача с самым неточным в мире ответом имеет дело с полными графами более высоких измерений. Обрисую вопрос в общих чертах, даже не пытаясь объяснить его. (Вам нужно только знать, что гиперкуб — это существующий в многомерном пространстве эквивалент двухмерного квадрата или трехмерного куба.) Итак, задача: каково минимальное количество измерений гиперкуба, чтобы получился полный граф с четырьмя точками, лежащими в одной плоскости, — при условии, что все линии, соединяющие все пары углов, двухцветные?
Еще никому не удалось ответить на этот вопрос, однако американский математик Рональд Льюис Грэм (р. 1935) нашел верхнюю границу ответа. Как 49 для R (5,5), верхняя граница — это число, для которого вы можете доказать, что оно больше правильного ответа либо равно ему.
Грэмовская верхняя граница являет собой столь огромное число, что для его записи потребовалась бы особая система счисления. И запись даже в такой системе счисления оказалась бы слишком длинной, чтобы включать ее в книгу. Достаточно лишь сказать следующее: число это столь огромно, что, если бы вся материя во Вселенной превратилась в перья и чернила, ее все равно не хватило бы, чтобы записать полученное значение в десятичной системе счисления.
И вот что самое забавное во всей этой истории: как было недавно подсчитано, правильный ответ может оказаться совсем не таким уж внушительным. Например, он вполне может равняться 11.
Зачастую, пользуясь компьютерами, мы не задумываемся о принципах их работы, так же как, крутя баранку, предпочитаем не вникать в процессы, происходящие под капотом. На такие показатели, как скорость обработки информации или размеры памяти, мы если и обращаем внимание, то лишь при покупке нового компьютера, но редко отдаем себе отчет, какого уровня развития достигли технологии, ставшие столь привычной частью современного мира.
Лучшую иллюстрацию тех небывалых свершений, на которые способны компьютеры, я вижу всякий раз, как набираю в поисковой системе «Гугл» очередное слово или фразу. Например, напечатав по-английски слово «type» («печатать, печать, шрифт»), я всего за 0,16 секунды (это время отображается на экране) получаю первую страницу списка из приблизительно 2 780 000 000 страниц интернет-сайтов, где встречается это слово. Информация о почти трех миллиардах страниц найдена менее чем за пятую долю секунды. Если вы наберете «movable type» («шрифт из подвижных литер»), всего через 0,2 секунды вам сообщат, что существует около 15 100 000 страниц, содержащих это словосочетание. А если набрать «the phrase “movable type”» («словосочетание “шрифт из подвижных литер”»), через 0,08 секунды придет ответ, что страниц с этой фразой найдено ровно восемь. Точнее, найдено восемь разных страниц, поскольку «Гугл» указывает, что если учитывать копии этих восьми страниц, то общее их число достигнет сорока.
Как же это происходит? Неужели где-то стоит компьютер, который по моему запросу считывает все содержимое Интернета и за долю секунды выбирает из него нужные мне страницы?