Яркий пример Эрдеша позволяет познакомиться с его уникальным характером. Этот эксцентричный математик, родившийся в Будапеште перед Первой мировой войной, большую часть своей взрослой жизни провел в путешествиях, редко задерживаясь на одном месте более чем на месяц. Он постоянно ездил по континентам от одного коллеги к другому, разыскивая новые решения для своего сборника математических задач. Если Эрдеш появлялся с чемоданом у вашей двери, предполагалось, что вы обеспечите ему кров и еду на столько времени, на сколько он захочет, спланируете и организуете его дела. Если у вас имелись дети, он называл их эпсилонами, намекая на обозначение, которое математики используют, когда хотят описать что-то бесконечно малое. У него также имелась какая-то задача, предназначенная для вас. Это было его величайшее умение – соединить какую-нибудь математическую проблему с тем самым человеком, который может помочь решить ее. На протяжении своей удивительно необычной карьеры, подпитываемой пристрастием к запрещенным веществам, венгерский математик написал более 1500 статей, причем большинство его работ были совместными: у него насчитывалось свыше 500 соавторов. Из-за таких методов ученые ввели число Эрдеша (это длина кратчайшего пути от данного человека до Эрдеша посредством совместных публикаций), и у большинства математиков число Эрдеша очень невелико[63].
У Рона Грэма число Эрдеша равно 1. Они были очень близкими людьми – настолько, что Грэм устроил в своем доме «комнату Эрдеша», где математик мог жить во время своих визитов и хранить вещи, когда уезжал. Грэм даже заботился о финансах Эрдеша, собирая его чеки и оплачивая счета. Однако к знаменитому числу Грэма венгерский математик отношения не имеет. Оно появилось благодаря сотрудничеству с другим американским математиком Брюсом Ли Ротшильдом, а затем с Мартином Гарднером, который вел рубрику математических развлечений в журнале Scientific American.
Грэм и Ротшильд занимались одной конкретной задачей из теории Рамсея. Чтобы понять ее, добавим к нашему званому ужину еще пару гостей – Грэма и Харольда. Грэм – дядя Беллы, а Харольд – какая-то загадка. Кажется, он свободно говорит на пяти разных языках, но никто толком не знает, кто он и чем занимается, да и разговаривает он мало, – возможно, он шпион. На самом деле это не имеет значения. Важно то, что теперь у нас есть восемь гостей, то есть мы можем расположить их в вершинах куба и создать сеть нового типа.
Предположим, я решил сделать через эту сеть какой-то разрез. Например, я мог бы провести его по диагонали через Беллу, Кларки, Эрнеста и Харольда. Эти четыре человека образуют своеобразную подсеть, которую гораздо проще нарисовать на плоском листе бумаги.
Но это не клика – это ничем не примечательное сочетание знакомых и незнакомых людей. Можно ли сделать более интересный разрез? В данном случае ответ положительный: проведя разрез по задней стенке куба через Эрнеста, Фонси, Грэма и Харольда, мы получим клику из четырех незнакомых попарно людей.
Грэму и Ротшильду хотелось узнать, в любом ли кубе всегда существует разрез, дающий такую клику. Если взять пространство трех измерений, то ответ отрицательный: существуют расстановки восьми гостей по вершинам куба, когда при любом разрезе клика не получится. Но, разумеется, математики не привязаны к трехмерному миру, поэтому Грэм и Ротшильд начали думать о гиперкубах в пространствах четырех, пяти, шести или любого другого числа измерений. Сколько измерений нужно взять, чтобы гарантировать клику на каком-нибудь разрезе?[64]
Не стоит и говорить, что Грэм и Ротшильд не смогли дать определенного ответа на этот вопрос, – так бывает с большинством задач в теории Рамсея. Однако они показали, что у задачи есть конечный ответ, и смогли дать для него оценку: это минимальное число измерений должно находиться между числом 6 и каким-то исполинским числовым монстром – неким конечным числом, превосходящим все, что мы когда-либо могли понять. Вопреки распространенному мнению, тот гигантский верхний предел, который они представили, – это не то, что мы сейчас называем числом Грэма[65]. То, что именуется сейчас числом Грэма, появилось шестью годами позже, в 1977 году, когда Рон общался с Мартином Гарднером. Математику требовался простой способ описать этот верхний предел для статьи Гарднера в Scientific American, поэтому он придумал нечто еще более грандиозное. В 1980 году это новое число попало в Книгу рекордов Гиннесса как «самое большое число, когда-либо использовавшееся в математическом доказательстве». Но на самом деле оно никогда в доказательствах не использовалось.
Неважно. Я хочу шокировать вас, заставив задуматься о величине числа Грэма, которое он показал Гарднеру. Не беспокойтесь. Я не собираюсь заставлять вас думать о его десятичном представлении. Во всяком случае, пока. Сейчас мы сосредоточимся на гораздо более безопасном способе представления числа Грэма, использующем стрелочную нотацию Кнута. Она названа в честь американского специалиста по информатике Дональда Кнута, который изобрел ее в 1976 году. Кнут много писал о числах и вычислениях и известен тем, что предложил вознаграждение в размере 2,56 доллара любому, кто обнаружит ошибку в какой-либо из его книг[66]. Его стрелки обеспечат нам безопасный проход через страну больших чисел.
Начнем с умножения: что мы подразумеваем, когда пишем 3 × 4? Возможно, вы хотите сказать «двенадцать», но давайте немного поразмыслим. На самом деле, когда мы пишем 3 × 4, мы имеем в виду, что тройка сложена сама с собой четыре раза, то есть 3 + 3 + 3 + 3. В общем виде это выглядит так:
Иными словами, a сложено с собой b раз. Разложив его таким образом, мы видим, что умножение – это просто затейливый способ описать повторяющееся сложение. А что насчет повторяющегося умножения?
Математики называют это возведением в степень и обычно записывают так:
Теперь a умножено на себя b раз. Например:
33 = 3 × 3 × 3 = 27;
34 = 3 × 3 × 3 × 3 = 81.
Вероятно, вы называете эти штуки степенями. Впрочем, неважно, как вы их называете, – лишь бы понимали, что это означает. Скажем, Дональд Кнут предложил собственный способ записывать степени – он предпочитает использовать стрелку:
Примеры выше можно записать в виде 3 ↑ 3 = 27 и 3 ↑ 4 = 81.
Здесь мы могли бы остановиться, и большинство нормальных людей так и сделает, но мы – не нормальные. Давайте продолжим. Что будет, если вы займетесь повторяющимся возведением в степень? Такая операция называется тетрацией. Кнут записывает ее в виде двойной стрелки:
Здесь к числу a мы b раз применяем операцию стрелки. Иначе тетрацию можно назвать степенной башней, поскольку вы можете изобразить ее в виде
где башня из букв a имеет b этажей.
Давайте найдем 3 ↑ ↑ 3 и 3 ↑ ↑ 4. Это степенные башни из троек: в одной три этажа, а в другой четыре. Иными словами:
3 ↑ ↑ 3 = 3 ↑ (3 ↑ 3) = = 327 = 7 625 597 484 987;
3 ↑ ↑ 4 = 3 ↑ (3 ↑ (3 ↑ 3))= 37 625 597 484 987.
Двойная стрелка позволяет нам одним прыжком переместиться от числа 3 до 7,6 трлн. Неплохое достижение. Однако нотация Кнута позволяет гораздо больше. Достаточно использовать тройную стрелку, считая ее повторением операции двойной стрелки:
Логика тут та же самая, но теперь к числу a мы b раз применяем операцию двойной стрелки. Тройная стрелка – это очень мощная штука. Попробуем найти 3 ↑ ↑ ↑ 3. Поскольку для тройной стрелки нужно несколько раз повторять операцию двойной стрелки, то мы получаем
3 ↑ ↑↑ 3 = 3 ↑ ↑ (3 ↑ ↑ 3) = 3 ↑ ↑ 7 625 597 484 987.
Да уж. Мы пришли к числу 3 ↑ ↑ 7,6 трлн. Это башня
в которой 7,6 трлн этажей! Представьте, что мы выписываем ее полностью: если каждая тройка будет иметь высоту два сантиметра, башня растянется до Солнца. Поэтому данное число иногда называют солнечной башней. Честно говоря, я боюсь его вычислять.
Но мы не собираемся на этом останавливаться.
Как насчет 3 ↑ ↑ ↑ ↑3? От этого реально сойти с ума. Если вы начнете вычислять, вы получите
Мы боялись вычислить даже солнечную башню, а теперь приходится иметь дело с солнечной башней двойных стрелок! Честно говоря, это уже просто неприлично. Гугол и гуголплекс давно за спиной. У нас нет ничего, что имело бы такой размер. Нужно признать, что мы вышли за рамки физической реальности. Но мы все еще и близко не подобрались к числу Грэма.
Выбора нет – надо продолжать.
В этом месте Грэм вводит понятие лестницы. Каждая ступенька – это число, которое намного больше всего предыдущего. Нижняя ступенька лестницы Грэма обычно называется g1, и это то самое монструозное число, с которым мы только что встретились:
g1 = 3 ↑ ↑↑ ↑ 3.
Шагаем на следующую ступеньку и внезапно обнаруживаем, что мы поднялись на
Посмотрите, сколько стрелок: их g1! Четырех уже было достаточно, чтобы породить чудовищное число, а теперь чудовищным стало количество стрелок. Монстр из монстров. Но мы все еще далеко от числа Грэма.
Сделаем еще один шаг по лестнице:
Нет смысла даже пытаться описать, насколько велико это число. Слова слишком сильно отстали от математики. Но надеюсь, вы видите закономерность: с каждой новой ступенькой на лестнице Грэма количество стрелок неимоверно увеличивается. Воздействие на само число вообще непостижимо. Итак, продолжаем подниматься: от g3 к g4, от g4 к g