Удивительные числа Вселенной - Антонио Падилья

знают Беллу, но не знакомы ни друг с другом, ни с другими гостями. Эрнест — инженер, дед которого занимался ввозом североамериканских серых белок в Британию (это тоже реальная история). Фонси — начинающий политик. В очередной раз обновляю диаграмму.

Уже сейчас, когда гостей всего шесть, сетка сплошных и пунктирных линий выглядит хаотично. Но если вы заглянете внутрь этого хаоса, то начнете видеть определенный порядок. Например, Алджернон, Кларки и Дино образуют так называемую клику — группу из трех человек, каждый из которых знает двух других[60]. Кларки, Эрнест и Фонси образуют клику другого рода: группу из трех попарно незнакомых между собой людей. При этом можно заметить, что нет ни одной такой клики из четырех человек.

Подобные сети лежат в основе теории Рамсея. На самом деле нет ничего удивительного, что на вечеринке с шестью гостями мы обнаружили такие клики из трех человек. Это неизбежно должно было произойти[61]. При этом шесть человек — минимальное количество, гарантирующее, что найдется тройка попарно знакомых или попарно незнакомых. Однако, как мы видели, шести гостей недостаточно, чтобы гарантировать аналогичную компанию из четырех человек. Оказывается, для этого нужно минимум восемнадцать гостей. Соответствующие числа называются числами Рамсея. Если пользоваться упрощенным математическим языком[62], можно сказать, что третье число Рамсея — 6, а четвертое — 18.

Рамсей показал, что можно получить клики любого конечного размера, если пригласить на вечеринку достаточно большое количество людей. Но он не смог определить, сколько именно людей придется созвать. Даже в случае клики всего из пяти человек ситуация резко усложняется. Большинство математиков считает, что для гарантированного получения клики из пяти человек требуется пригласить минимум 43 гостя, однако точный ответ никому не известен. Минимальное число находится где-то между 43 и 48.

Чтобы определить его точно, математикам требуется изобразить все возможные сети и посмотреть, где гарантированно возникнут клики из пяти элементов. Для этого можно попробовать привлечь компьютер, однако вам просто не хватит вычислительной мощности. Когда есть 43 гостя, вы поручаете компьютеру изучить 2903 разных сетей. Это число значительно больше гугола. Даже современные суперкомпьютеры отказываются работать с такими числами.

Чтобы гарантировать клику из шести человек, минимальное число гостей должно быть где-то между 102 и 165. Очевидно, что проблема нахождения точного значения шестого числа Рамсея значительно сложнее, чем нахождение пятого. Великий странствующий математик Пал Эрдеш предложил следующее апокалиптическое описание ситуации. Представьте вторжение инопланетян — армию пришельцев, намного опередивших нас в развитии. Они высадились на Землю и потребовали, чтобы мы сообщили им пятое число Рамсея, а иначе они уничтожат нашу цивилизацию за глупость. Стратегия Эрдеша для этого случая заключалась в том, чтобы объединить мощь всех компьютеров мира и довериться математикам, которые дадут ответ на вопрос. Но если бы пришельцы потребовали шестое число Рамсея, то такая стратегия бессмысленна. В этом случае придется искать способ уничтожить инопланетян до того, как они уничтожат нас.

Яркий пример Эрдеша позволяет познакомиться с его уникальным характером. Этот эксцентричный математик, родившийся в Будапеште перед Первой мировой войной, большую часть своей взрослой жизни провел в путешествиях, редко задерживаясь на одном месте более чем на месяц. Он постоянно ездил по континентам от одного коллеги к другому, разыскивая новые решения для своего сборника математических задач. Если Эрдеш появлялся с чемоданом у вашей двери, предполагалось, что вы обеспечите ему кров и еду на столько времени, на сколько он захочет, спланируете и организуете его дела. Если у вас имелись дети, он называл их эпсилонами, намекая на обозначение, которое математики используют, когда хотят описать что-то бесконечно малое. У него также имелась какая-то задача, предназначенная для вас. Это было его величайшее умение — соединить какую-нибудь математическую проблему с тем самым человеком, который может помочь решить ее. На протяжении своей удивительно необычной карьеры, подпитываемой пристрастием к запрещенным веществам, венгерский математик написал более 1500 статей, причем большинство его работ были совместными: у него насчитывалось свыше 500 соавторов. Из-за таких методов ученые ввели число Эрдеша (это длина кратчайшего пути от данного человека до Эрдеша посредством совместных публикаций), и у большинства математиков число Эрдеша очень невелико[63].

У Рона Грэма число Эрдеша равно 1. Они были очень близкими людьми — настолько, что Грэм устроил в своем доме «комнату Эрдеша», где математик мог жить во время своих визитов и хранить вещи, когда уезжал. Грэм даже заботился о финансах Эрдеша, собирая его чеки и оплачивая счета. Однако к знаменитому числу Грэма венгерский математик отношения не имеет. Оно появилось благодаря сотрудничеству с другим американским математиком Брюсом Ли Ротшильдом, а затем с Мартином Гарднером, который вел рубрику математических развлечений в журнале Scientific American.

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

Предположим, я решил сделать через эту сеть какой-то разрез. Например, я мог бы провести его по диагонали через Беллу, Кларки, Эрнеста и Харольда. Эти четыре человека образуют своеобразную подсеть, которую гораздо проще нарисовать на плоском листе бумаги.

Но это не клика — это ничем не примечательное сочетание знакомых и незнакомых людей. Можно ли сделать более интересный разрез? В данном случае ответ положительный: проведя разрез по задней стенке куба через Эрнеста, Фонси, Грэма и Харольда, мы получим клику из четырех незнакомых попарно людей.

Грэму и Ротшильду хотелось узнать, в любом ли кубе всегда существует разрез, дающий такую клику. Если взять пространство трех измерений, то ответ отрицательный: существуют расстановки восьми гостей по вершинам куба, когда при любом разрезе клика не получится. Но, разумеется, математики не привязаны к трехмерному миру, поэтому Грэм и Ротшильд начали думать о гиперкубах в пространствах четырех, пяти, шести или любого другого числа измерений. Сколько измерений нужно взять, чтобы гарантировать клику на каком-нибудь разрезе?[64]

Не стоит и говорить, что Грэм и Ротшильд не смогли дать определенного ответа на этот вопрос, — так бывает с большинством задач