Удивительные числа Вселенной полностью

Как видите, деревья — просто кружки, соединенные линиями. Кружки — семена, а линии — ветви. В нашем примере есть три разных типа семян: черные, белые и крестики. Правила игры таковы: когда вы строите лес, первое дерево должно иметь не более одного семени, второе — не более двух и т. д. Лес умирает, если вы строите дерево, которое содержит одно из предыдущих деревьев. У выражения «содержит одно из предыдущих деревьев» есть точное математическое значение, но, возможно, достаточно представить яблоню. Яблони могут стоять отдельно, а могут вырастать из других деревьях. Возможно, где-нибудь в лесу вы видите определенную яблоню, а затем обнаруживаете какую-то большую сосну, из ствола которой торчит точная копия этой яблони. Такая ситуация в Игре деревьев запрещена.

Чтобы дать более точное определение, сравним несколько деревьев и спросим, «содержит» ли одно из них другое. Например, рассмотрим следующие различные деревья.

Содержит ли дерево A дерево B? Ответ довольно очевиден. Конечно, дерево А содержит дерево B — это видно по верхним ветвям. А что насчет дерева С? Содержится ли и оно в дереве А? На первый взгляд кажется, что нет, но подумайте, что произойдет, если вы прикроете белое семя в центре дерева А. То, что остается, по сути является деревом С. Таким образом, в этом смысле вы можете утверждать, что дерево А действительно содержит дерево С.

Чтобы разобраться с ситуацией, нужно поближе взглянуть на свод правил. Чтобы одно дерево содержало другое, мы должны уметь сопоставлять соответствующие семена, как сделали в вышеприведенном примере, прикрыв белое семя дерева А. Но одного этого недостаточно. Соответствующие друг другу семена также должны согласовываться по своему ближайшему общему предку. Для любых двух семян на верхних ветвях дерева вы можете найти их ближайшего общего предка, прослеживая их родословную в сторону корня и обнаружив то семя, где эти две линии сходятся. Представьте, что семена — это вы и ваш двоюродный брат. Если вы пойдете по своим родословным, эти линии сойдутся у ваших общих бабушки и дедушки.

Посмотрите на черное семя и крестик на верхних ветвях дерева А и дерева С. Прослеживая родословную в обоих случаях, мы видим, что в случае дерева А их ближайший общий предок — белое семя, а в случае дерева С — черное. Таким образом, получилось расхождение. Соответственно, в этом более слабом смысле дерево А не содержит дерево С.

Проясним ситуацию еще на одном примере. Вот еще два дерева.

Содержит ли дерево D дерево E? Первое, что нужно проверить: можем ли мы привести в соответствие семена? Закрываем все семена-крестики в дереве D и видим, что можем. Теперь нам нужно задаться вопросом о предках. Обратите внимание на белое и черное семена в верхних ветвях обоих деревьев. Проследив их родословную, мы видим, что в обоих случаях ближайшим общим предком оказывается черное семя, находящееся в корне. Подходит по всем статьям. Дерево D действительно содержит дерево E.

Теперь, когда правила понятны, мы готовы играть. Возьмем вариант, когда нам разрешено пользоваться только черными семенами. Я делаю ход первым. Помните, что это первое дерево, поэтому в нем может быть максимум одно семя. Изобразим его так.

Ваш ход. И у вас сразу же неприятности. Поскольку это второе дерево в лесу, в нем может быть не больше двух семян. Существует только два возможных дерева, которые вы можете изобразить: либо еще одно дерево из одного семени, либо дерево из двух семян.

Однако очевидно, что мое дерево содержится в обоих ваших возможных деревьях. Какое бы из них вы ни посадили, лес умрет. Избежать этого невозможно, поэтому игра заканчивается после первого же хода. Если использовать только один тип семян, лес может состоять только из единственного дерева, состоящего из одного семени.

Теперь давайте поиграем, когда разрешены два различных типа семян. Игра гарантированно закончится после трех ходов.

Какое бы дерево вы ни посадили дальше, оно обязательно уничтожит лес. Я догадываюсь, что вы не слишком впечатлены. Кому захочется играть в игру, которая обязательно закончится после трех жалких ходов?

Но подождите.

Пришло время сыграть с семенами трех видов — черные, белые и крестики. Давайте попробуем сделать несколько ходов.

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

Гораздо позже.

В этой книге мы уже читали истории о числовых исполинах — числах непостижимых размеров. Но эти колоссы — ничто по сравнению с нашим следующим левиафаном. Число, которое обозначают TREE(3), — гигантское предельное число ходов в игре с тремя семенами. Оно входит в крайне экстравагантную последовательность TREE(n). Если вы играете в Игру деревьев с n различными семенами, то игра закончится через TREE(n) ходов. Взгляните, как неспешно она начинается.

TREE(1) = 1 (поскольку игра с одним семенем продлится всего один ход),