Форма реальности Элленберг Джордан

Геометрические объекты интересны широкому кругу людей, потому что они перекликаются с реальными вещами, с которыми мы периодически сталкиваемся в жизни. Если бы единственными треугольными предметами во Вселенной были металлические ударные музыкальные инструменты, то мы уделяли бы изучению треугольников гораздо меньше внимания.

С помощью дерева можно изобразить не только игру. Та же геометрия есть повсюду. Разумеется, в настоящих деревьях с корой, которые поглощают углекислый газ. В генеалогических (родословных) деревьях, где ветви определяются не выбором вариантов, а рождением детей. Корень родословного древа – это пара-основатель, конечные точки-листья – это члены семьи, у которых не было (или пока нет) детей. Обычно генеалогическое древо изображают с корнем вверху: мы называем себя потомками и находимся на нисходящей линии от предков.

Артерии в нашем теле тоже образуют дерево. Корень – это аорта, большая трубка, несущая насыщенную кислородом кровь от сердца; от нее отходят правая и левая коронарные артерии, плечеголовной ствол, левая общая сонная артерия, левая подключичная артерия, бронхиальные артерии, пищеводные артерии… Каждая из них, в свою очередь, делится на более мелкие артерии; плечеголовной ствол – на правую общую сонную артерию и правую подключичную артерию; правая общая сонная артерия разветвляется на внешнюю и внутреннюю сонные артерии примерно там, где подбородок соприкасается с шеей, и так далее, вплоть до крохотной сети артериол диаметром в один-два волоса – последней остановки крови перед тем, как она избавится от кислорода и начнет свое путешествие обратно к легким за его новой порцией.

Не у всех внутри одинаковое кровеносное дерево! Иллюстрация выглядит похожей на тест для иностранцев с несколькими ответами, хотя на самом деле на ней изображены разновидности ветвления артерий[187], питающих нашу печень.

Река – это дерево[188]. Только помните, что двигаться тут надо против течения. Корень – это залив или море, куда впадает река. Отсюда вы поднимаетесь по ней, а она тем временем разветвляется на притоки, затем на притоки притоков и так далее – вплоть до истока.

То же самое относится к любой иерархической классификации, например линнеевской классификации биологических видов. Царства делятся на отделы, отделы – на классы, классы – на порядки, порядки – на семейства, семейства – на роды, роды – на виды. Вот дерево деревьев:

Добро и зло – тоже деревья! Speculum Virginum («Зеркало девственниц») – это дидактический трактат для средневековых монахинь, составленный, как принято считать, монахом-бенедиктинцем Конрадом из монастыря Хирзау в Шварцвальде в XII веке, хотя вопросы авторства в истории литературы столь отдаленного времени крайне сложны. Тем не менее эта книга существует и в ней есть Древо Добродетелей и Древо Пороков. Зло интереснее, так что обратимся к порокам[189].

Корень дерева, источник всех пороков, – это superbia (гордыня), прорастающая из головы какого-то богато одетого господина. Потомки гордыни включают ira (гнев), avaritia (алчность), а в верхней части страницы – luxuria (похоть, блуд), слово, услужливо начертанное на тазе улыбающегося мужчины. У каждого из грехов есть собственные потомки: семь отпрысков гнева включают богохульство и оскорбление, а похоть порождает libido, fornicario и turpitudo. (Не могу сказать, что улавливаю между ними тонкие различия[190], и это одна из причин, почему из меня получилась бы плохая средневековая монахиня.)

С течением времени проблемы людей становятся не столько этическими, сколько корпоративными, а дерево возвращается в виде организационной диаграммы – схемы, показывающей структуру взаимоотношений внутри компании. Такое дерево сообщает, кто кому подчиняется и кто кому приказывает. Вот, возможно, первая такая схема, составленная инженером Дэниелом Маккаллумом в 1855 году для железной дороги Нью-Йорка и Эри. Впоследствии Маккаллум будет руководить всеми железными дорогами сил Союза во время Гражданской войны[191].

Информация течет от листьев обратно к корню, президенту железной дороги, в то время как власть течет в противоположном направлении: от президента через цепочки подчиненных к листьям и почкам, которые напечатаны слишком мелко, чтобы их можно было прочитать на этой странице: рабочие, машинисты, плотники и смазчики[192]. Эта диаграмма не совсем дерево; на ней организационная структура сочетается с изображением железнодорожных линий, которыми управляет организация. В центре она похожа на Древо Пороков, а по краям – на американские пригороды конца XX века, если смотреть на них сверху. Дерево отображает геометрию иерархии по тем же причинам, по которым оно представляет геометрию игры «Ним» или геометрию сада расходящихся тропок[193], составляющих нашу жизнь; нет циклов, нет бесконечного возвращения. Если я руковожу вами, то вы не можете руководить мной. Если одна позиция в «Ниме» следует из другой, то ни один ход не может вернуть вас в предыдущее состояние; это то, что мешает играм длиться вечно[194].

Но больше артерий, рек и грехов мне нравятся деревья чисел. Вот как они создаются. Вы начинаете с какого-нибудь числа, скажем 1001, и затем рубите его топором. Я имею в виду, что вы находите два меньших числа, произведение которых равно 1001. Например, 1001 = 13  77. А теперь рубим топором каждый из множителей. Мы можем разрубить 77 на 7  11. А 13? Вот здесь мы застряли: это число нельзя представить в виде произведения двух меньших чисел. Машите топором, сколько хотите, все равно ничего не выйдет. То же самое верно для 7 и 11. Мы можем записать то, что только что сделали, в виде дерева, где каждая ветвь изображает удар топора.

Листья дерева – числа, которые уже не разбиваются, – мы называем простыми числами, базовыми кирпичиками лего, из которых составлены все числа. Все числа? Откуда я это знаю? Благодаря дереву. На каждом этапе размахивания топором число, на которое мы нацелились, либо делится на два меньших множителя, либо нет, и если не делится, то оно простое. Мы рубим до тех пор, пока не сможем больше рубить. И в этот момент все оставшиеся числа оказываются простыми. Это может занять много времени, если мы начнем, например, с 1024:

или получиться сразу, если начать с простого числа вроде 1009:

Однако рано или поздно это произойдет.

Такой процесс не может продолжаться вечно, поскольку с каждым ударом топора числа в дереве становятся меньше, а последовательность целых положительных чисел, которые уменьшаются на каждом шаге, в итоге должна достигнуть конца и остановиться[195].

В финале этого фестиваля рубки получается дерево, все листья которого – числа, не раскладывающиеся на множители, то есть простые числа, и если их все перемножить, то мы получим число, с которого начали.

Тот факт, что любое целое число[196], каким бы большим и сложным оно ни было, можно выразить как произведение простых множителей, вероятно, впервые был доказан примерно в конце XIII века персидским математиком (и пионером в оптике – в те времена специализация была менее распространена) Камалом ад-Дин аль-Фариси в трактате (Тадхкират аль-Ахбаб фи байан аль-Тахабб «Записки для друзей о доказательстве дружественности»[197]).

С учетом вышесказанного это может показаться странным. Почему потребовалось почти две тысячи лет, чтобы пройти от определения простого числа у пифагорейцев до теоремы аль-Фариси? Здесь снова причина в геометрии. Евклид определенно понимал факты, из которых для современного специалиста по теории чисел немедленно следует вывод, что любое простое число можно разложить на простые: некоторые на кучу простых, как 1024, или только на одно, как 1009, или на нечто среднее, как 1001. Однако Евклид не пишет о произведениях большого количества простых множителей, и мы предполагаем, что причина в том, что он просто не мог этого сделать. Для Евклида все было геометрией, поэтому любое число он представлял как длину какого-то отрезка. Сказать, что число делится на 5, – значит сказать, что на этом отрезке укладываются пять одинаковых отрезков меньшей длины. Когда Евклид умножает два числа, он представляет результат в виде площади прямоугольника, длина и ширина которого – те два числа, что мы перемножили (сомножители). Когда Евклид умножает три числа, он называет результат телесное, поскольку воспринимает его как объем прямоугольного кирпича с длиной, шириной и высотой, равными сомножителям[198].

Математика в основе своей – творческое занятие, которое задействует все наши когнитивные и творческие способности. Когда мы занимаемся геометрией, мы используем то, что наш разум и тело знают о размерах и форме тел в пространстве. Евклид добился успехов в теории чисел не в перерывах между занятиями геометрией, а благодаря своим работам по геометрии. Воспринимая числа как длины отрезков, он смог понять их лучше своих предшественников. Однако привязка теории чисел к геометрической интуиции одновременно и ограничивала его. Произведение двух чисел было площадью прямоугольника, а трех чисел – объемом кирпича-параллелепипеда. А произведение четырех чисел? Это не та величина, которую можно реализовать в трехмерном пространстве, где мы живем. Поэтому такие величины Евклид обходит молчанием. Более алгебраический подход математиков средневековой Персии был не так сильно привязан к нашему физическому опыту и поэтому лучше способствовал переходу к чисто умственным абстрактным сферам. Однако это не означает, что в нем нет геометрии. Как мы уже видели, геометрия не ограничивается тремя измерениями, их может быть сколько угодно. Просто нужно больше напряжения при воображении. Мы доберемся и до этого.

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

Но кто?

Оказывается, дерево может нам сказать и это.

Фокус в том, чтобы начать с конца игры. Это самый простой способ определить, кто выигрывает! Если камней не осталось, то тот, кто только что сделал ход, выиграл. Так что, если моя очередь ходить, а камней нет, я проиграл. Чтобы отследить это, я украшу дерево игры, нарисованное ранее, надписав букву П над всеми позициями, где нет камней. Это напомнит нам, что я проигрываю, если окажусь в одной из этих позиций при своем ходе.

А если есть всего один камень? Тогда у меня только один вариант. Я беру камень и выигрываю. Поэтому я пишу букву В над каждой такой позицией.

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

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

Вот так на данный момент выглядит наше дерево.

Теперь можем продолжить, двигаясь назад во времени шаг за шагом. Две кучки, в одной два камня, а в другой один? У нас есть три варианта хода: убрать меньшую кучку, убрать большую кучку или взять из нее один камень. Получающиеся позиции уже обозначены В, В, П. Но поскольку один из ходов означает проигрыш моего противника, мне следует выбрать именно его, и данная позиция получает букву В. Игрок, которому осталась позиция с двумя кучками или одной, выигрывает, если сделает верный ход.

Вы выигрываете, когда ваш противник вынужден проиграть. Звучит как мотивационный плакат в спортзале, но на самом деле это математика. На языке деревьев это означает следующее: «Обозначайте позицию буквой В, если в ней существует ветвь, ведущая в позицию П». По тем же соображениям обозначайте позицию буквой П, если это не так. Ведь это означает, что при любом выборе вы оставляете оппоненту позицию В. Вы проигрываете, когда ваш оппонент может победить, что бы вы ни делали.

Все сводится к следующему.

ДВА ПРАВИЛА

Первое правило. Если каждый мой ход ведет в позицию В, то моя текущая позиция – П.

Второе правило. Если какой-то сделанный мной ход приведет в позицию П, то моя текущая позиция – В.

Эти два правила позволяют нам системно маркировать любое положение буквами П или В – вплоть до корня, с которого мы начинали игру. При этом мы никогда не зациклимся, потому что у деревьев нет циклов.

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

Я могу описать этот процесс словами, но стоит ли? Чтобы досконально с ним разобраться, нужно поиграть самому. Позовите друга, предложите поиграть в «Ним» с двумя кучками по два камня. Пусть ваш друг ходит первым (поскольку вы, возможно, не такой уж и хороший друг). А теперь используйте нарисованное выше дерево для выбора ходов. Выигрывайте, выигрывайте и выигрывайте. Так вы прочувствуете, как это работает.

Метод дерева работает для игры «Ним» с большим количеством кучек и камней, то есть для всех вариантов игры. Хотите знать, кто выиграет с двумя кучками по 20 камней в каждой? Можете нарисовать большое дерево, спуститься по нему и выяснить это. (Побеждает Джефф.) Две кучки по 100 камней? (Все равно Джефф.) Одна куча из 100 камней, а вторая из 1000? (Здесь победит Акбар[199].) Более того, промаркированное дерево не просто говорит вам, кто победит, – оно показывает, как побеждать. Если вы находитесь в позиции В, то знаете, что как минимум один ход ведет в положение П, – сделайте его. Если вы в положении П, философски пожмите плечами, сделайте произвольный ход и надейтесь, что противник накосячит.

В случае, когда в игре «Ним» только две кучки, можно избежать утомительной маркировки всего дерева, применив более простой (и, честно говоря, более красивый) способ выяснить, кто победит, использующий симметрию левого и правого. Помните, насколько проще доказательство Паппа для моста ослов, основанное на симметрии, чем исходное евклидово? С «Ним» во многом то же. Предположим, что Акбар и Джефф начинают игру с двумя кучками по 100 камней в каждой. Хотите рисовать такое дерево? Я тоже не хочу. Поэтому есть способ получше. Думаю, вам знакома такая невероятно раздражающая ситуация, когда младший ребенок повторяет все за старшим? «Прекрати за мной повторять». «Прекрати за мной повторять». «Ты надоел». «Ты надоел». И так далее. Что ж, представьте, что Джефф выбрал такую тактику в игре. Что бы ни сделал Акбар, Джефф повторяет его действие на другой кучке. Акбар берет 15 камней из левой кучи, оставляя 85? Тогда Джефф берет 15 камней из правой; теперь в обеих кучах по 85 камней. Акбар переключается на правую кучу и забирает 17 камней, оставляя 68? Джефф делает то же самое с левой. Джефф всегда зеркально отражает действия Акбара, постоянно уравнивая стопки. В частности, Джефф никогда не сможет первым забрать всю кучу, потому что всего лишь повторяет действия Акбара. Поэтому Акбар первым покончит с одной из кучек, и тогда Джефф повторит это действие на другой кучке и выиграет. Следовательно, игра «Ним» с двумя равными кучами – это победа Джеффа. Его стратегия столь же непобедима, сколь и раздражительна.

А если кучки не одинаковы по размеру? Тогда Акбар, который ходит первым, уравняет в них количество камней. Теперь уже Джефф будет раздраженным старшим братом, потому что с этого момента Акбар будет повторять все его ходы и в итоге выиграет. На языке двух правил Акбар использует свой ход, чтобы добиться позиции с двумя равными кучами, которая – в соответствии с предыдущим абзацем – имеет маркировку П; и если вы можете попасть в П, то, по второму правилу, текущая позиция – В.

Когда у вас больше двух куч, простое соображение о симметрии не работает. Тем не менее все равно есть способ узнать, кто победит, не рисуя дерево целиком. Мы не станем описывать здесь все решение, включающее перевод количества камней во всех кучах в двоичную систему, но вы можете его найти в удивительно яркой, глубокой и богатой идеями книге Элвина Берлекэмпа, Ричарда Гая и Джона Конвея Winning Ways for Your Mathematical Plays («Выигрышные стратегии в математических играх»), наряду с другими играми, такими как «Хакенбуш», «Снорт», «Рассада», и объяснением, почему каждая игра в итоге – своего рода число.

В варианте игры «Ним» под названием «Игра с вычитанием» вы начинаете с одной кучи камней и вам разрешается взять только 1, 2 или 3 камня. Побеждает игрок, взявший последний камень. Эта игра тоже представляет собой дерево, и вы можете аналогичным образом проанализировать ее, начиная с конца. Эта версия «Ним» получила известность благодаря появлению в качестве задания для участников пятого сезона реалити-шоу Survivor («Последний герой»), который снимался в Таиланде. (Там игру назвали не «Ним» и не «Игра с вычитанием», а «Тай 21», хотя у нее нет тайских корней; возможно, такое название ориентировано на американскую аудиторию, которая склонна считать вещи азиатского происхождения мудреными и непостижимыми.) По той же причине сохраняется неискоренимая традиция описывать «Ним» как древнюю китайскую игру, хотя это, видимо, полностью вымышлено: впервые она упоминается[200] в книге математических головоломок и фокусов Луки Бартоломео де Пачоли, который был другом Леонардо да Винчи, францисканским монахом и общепризнанным «отцом двойной бухгалтерии». (Неужели это менее интересно, чем происхождение из Древнего Китая?)

Особенность шоу Survivor в том, что его принято считать одним из самых глупых на телевидении, хотя в действительности оно одно из самых умных. Вы много видели шоу, где в реальном времени можно наблюдать, как люди думают? Не говоря уже о занятиях математикой?! Именно это предлагает шестой эпизод пятого сезона шоу Survivor. Тед Роджерс – младший, крупный сильный мужчина, поигравший совсем недолго за «Даллас Ковбойс»[201], берет на себя инициативу и говорит сокомандникам: «В конце нам надо сделать так, чтобы осталось четыре флага». (В версии игры для шоу используются не камни, а флаги.) «Пять или четыре?» – уточняет Джейн Джентри, леди из Техаса из группы Роджерса. «Четыре», – настаивает мужчина.

Роджерс в уме проделал то же вычисление, что и мы для игры «Ним», подойдя к задаче с позиции математика – с конца. Это неудивительно: в глубоких зонах мозга, выстраивающих стратегии, все мы – математики, независимо от того, что написано на наших визитках.

Если остался один флаг, то это буква В; вы забираете его и выигрываете. С двумя и тремя флагами ситуация не меняется, поскольку у вас остается возможность забрать все флаги и победить. А как насчет четырех флагов?

Какой бы ход участники шоу ни сделали, они оставляют противникам букву В. Поэтому, согласно второму правилу, четыре флага – это П. Большой Тед прав: оставьте второй команде четыре флага – и обеспечите себе победу. Оппоненты это тоже осознали, но поздно: взяв три флага из девяти и оставив шесть, они ошеломленно смотрят друг на друга, и один из них говорит: «Если они берут два, мы проиграем». Увы, противники делают это и выигрывают[202].

Запоздалое озарение их не спасло, но оно все еще полезно для нас. Почему невыгодно оставаться с четырьмя флагами? Потому что на каждый ваш ход противник дает естественный ответ. Вы берете два, и они два. Вы один, они – три. Вы три, они – один. Во всех случаях все четыре флага разобраны, игра окончена, победитель не вы.

Так что правильная игра – оставить оппоненту четыре флага. И если перед вашим ходом их пять, шесть или семь, то нужно оставить противнику фатальную четверку. Но если перед вами восемь флагов, то в вашем шардоне плавает черная муха. Возьмете три – оппоненты возьмут один. Возьмете два – они тоже два. Возьмете один – они три. И с четверкой встречаетесь вы.

Звучит знакомо? Потому что начать с восьми флагов – все равно что с четырех. Что бы вы ни сделали, ответным ходом противник уменьшает суммарное количество флагов на четыре. Начать с двенадцати – все равно что начать с восьми, а начать с шестнадцати – все равно что с двенадцати и так далее…

Если вы начинаете с количества флагов, кратного четырем, вы проиграете; в противном случае выиграете, но при условии, что будете брать верное число флагов, чтобы оставлять противнику фатальные числа.

Поздравляю! Мы только что доказали теорему.

Подобным рассуждениям (о доказательстве) нужно учить на уроках математики, и особенно геометрии. Мы наблюдаем (возможно, чисто мысленно или сыграв много раз), что четыре или восемь флагов – это проигрышные состояния; анализируем и начинаем понимать, почему проигрывают не только четыре, восемь, но и любое число, кратное четырем. После этого при желании можно выстроить более формальную цепочку рассуждений, показывающую, что вы проигрываете каждый раз, когда число флагов кратно четырем.

Доказательство – это кристаллизованная мысль. Оно берет блестящий радостный момент «понимания» и фиксирует его на странице, чтобы мы могли поразмышлять над ним на досуге. Что еще важнее, мы можем поделиться доказательством с другими людьми, в чьем сознании оно снова оживает, словно одна из тех выносливых микробных спор[203], которые настолько жизнестойки, что могут выдержать путешествие в космос на метеорите и колонизировать новую планету после удара. Доказательство позволяет мыслям перемещаться. Считается, что мы, математики, стоим на плечах гигантов, но я предпочитаю говорить, что мы идем по лестнице застывших мыслей обычных людей. Мы добираемся до вершины, окропляем своими мыслями лед, они примерзают к нему и делают лестницу еще выше. Может, это не столь выразительно, зато гораздо правдивее.

Я сказал, что мы доказали теорему. Нужно ли нам записать доказательство? Давайте запишем.

Теорема флагов: если количество флагов равно 4, 8, 12 или любому числу, кратному 4, то первый игрок проигрывает; в противном случае первый игрок выигрывает, выбирая такое количество флагов, чтобы противнику оставалось число, кратное 4.

А теперь доказательство. Может быть, вы уже сочли мои рассуждения убедительными. Надеюсь, что так! Однако в них есть слабое место – словосочетание «и так далее…». Это многоточие указывает на нечто недосказанное, а в доказательстве такого быть не должно.

Что происходит, когда мы пытаемся озвучить невысказанное? Мы упомянули 4, 8, 12 и 16 флагов, но не 20, поэтому могли бы добавить в обсуждение и их. Но тогда нам нужно было бы рассмотреть случай с 24 флагами, а это неизбежно приведет к варианту с 28 флагами. И так далее. Вот в чем настоящая проблема! Бесконечно длинное доказательство бесполезно! Кто будет его читать? И все же такая ситуация отдает некоторым пренебрежением – человек машет руками и говорит: «Я мог бы продолжать и дальше, но не буду».

Попробуем действовать иначе. Например, разобьем теорему флагов на две части.

ТФ1. Если количество флагов равно 4, 8, 12 или любому кратному числа 4, то первый игрок проигрывает.

ТФ2. Если количество флагов не равно числу, кратному 4, то первый игрок выигрывает.

Почему мы считаем, что утверждение ТФ1 истинно? Потому что, сколько бы флагов мы ни взяли, у противника остается количество флагов, не кратное 4. Поэтому, согласно ТФ2, такая ситуация отмечается буквой В, а значит, по второму правилу, моя текущая позиция – П. Таким образом, утверждение ТФ1 истинно, если утверждение ТФ2 истинно. На языке логики мы бы сказали: из ТФ2 следует ТФ1.

Похоже, наметился прогресс! Нам нужно было доказать две вещи, а теперь только одну. Так почему ТФ2 истинно? Предположим, что количество флагов не кратно 4. Тогда вы можете его уменьшить до кратного 4, взяв 1, 2 или 3 флага[204]. Теперь, согласно ТФ1, вы поставите оппонента в положение П. Но если вы можете перевести текущую позицию в П, то, исходя из первого правила, сама текущая позиция – В.

Итак, подытожим: ТФ1 истинно, поскольку ТФ2 истинно, а ТФ2 истинно, потому что истинно ТФ1.

Ой-ой-ой!

Уж очень напоминает порочный круг – то самое печальное рассуждение, когда вы воспринимаете утверждение как его собственное обоснование. Большинство из нас слишком умны, чтобы уговорить себя применить это непосредственно, поэтому мы строим небольшой цикл утверждений, где каждое последующее вытекает из предыдущего.

«Я не верю ничему, прочитанному в газете “Сердитый знаток”, ей верить нельзя. Откуда я знаю, что ей нельзя верить? Потому что там вечно публикуют лживые истории. Откуда я знаю, что они лживые? Потому что я читаю их в газетенке “Сердитый знаток”, а ей не стоит верить».

Получилась своего рода математическая ловушка.

К счастью, выход есть. Подумайте снова о нашем исходном аргументе, который (если не считать досадного многоточия) был весьма убедителен, и это вполне справедливо. Ведь он опирался на нисходящую схему: вы доказали факт о шестнадцати флагах, используя факт о двенадцати, который, в свою очередь, доказали с помощью факта о восьми, а его, в свою очередь, с помощью факта о четырех флагах. Такой процесс не может длиться вечно и должен прекратиться, потому что целые положительные числа не могут бесконечно уменьшаться. Это тоже геометрия! На непрерывном пути мы можем просто приближаться к конечной точке, делая бесконечное число все более крошечных шажков. Однако геометрия целых чисел дискретна, а не непрерывна; они похожи на последовательность камней, по которым вы прыгаете. На вашем пути не так много камней, и в конце концов он заканчивается. Звучит несколько знакомо, верно? Да потому что мы уже говорили об этом несколько страниц назад, когда обсуждали, что факторизация чисел в итоге приводит к куче простых множителей, которые уже разложить нельзя. Используемый здесь метод называется математической индукцией и в каком-то смысле восходит к тому факту о разложении на простые множители, который аль-Фариси предложил семьсот лет назад.

Нужное рассуждение будет доказательством от противного, которое сейчас для большинства математиков стало почти рефлекторной привычкой. Что бы вы ни хотели доказать, вы предполагаете обратное. Звучит странно и неправильно, зато это чрезвычайно полезно. Например, вы делаете предположение, что ошибаетесь насчет мироустройства, и начинаете обдумывать его, всячески переворачивая и строя цепочки следствий, пока (надеюсь!) не придете к заключению, что оно не может быть правильным. Это все равно что держать твердый леденец во рту, который постепенно растворяется и растворяется, пока не дойдет до кислого противоречия в центре.

Итак, допустим, что мы заблуждаемся в справедливости теоремы флагов. Тогда должен быть контрпример: какое-то плохое количество флагов, для которого теорема говорит, что мы проигрываем, хотя на самом деле выигрываем, или что мы выигрываем, хотя на самом деле проигрываем. Возможно, таких плохих чисел будет несколько. Однако вне зависимости от их количества среди них есть наименьшее.

В этот момент на сцену выходит алгебра. Иногда люди впадают в панику при появлении x или y. Полезно думать о таких символах как о местоимении. Бывает, что вы хотите обратиться к человеку, но не знаете его имени. Может быть, вы даже не знаете, кто именно этот человек. Скажем, говоря о следующем президенте Соединенных Штатов, вы используете местоимения он или она не потому, что у этого человека нет имени, а потому, что вы пока его не знаете. Поэтому давайте назовем самое маленькое плохое число N. Напоминаем, что слово «плохое» означает следующее: либо N кратно 4, но при этом позиция выигрышная, либо N не кратно 4, но при этом позиция проигрышная.

Допустим, N кратно 4, тогда, что бы я ни делал (брал 1, 2 или 3 флага), результат не будет кратным 4. Более того, он будет меньше N, а потому не может быть плохим. Это важный момент в доказательстве, так что остановитесь и полюбуйтесь. N не просто плохое число, это наименьшее плохое число. Все числа меньше N не являются плохими, а потому ведут себя в соответствии с теоремой флагов. А она утверждает, что если число флагов не кратно 4, то позиция выигрышная. Чувствуете привкус противоречия? Предполагалось, что позиция с N флагами выигрышная, однако оказалось, что любой ваш ход оставляет выигрышную позицию противнику. Этого не может быть. Противоречие.

Рассмотрим второй случай. N не кратно 4, но при этом позиция проигрышная. Однако, независимо от N, я могу взять 1, 2 или 3 флага и оставить второму игроку число флагов, кратное 4. Это новое число меньше N, а потому не может быть плохим и подчиняется теореме флагов, а значит, позиция должна быть проигрышной. Но если я могу оставить оппоненту проигрышную позицию, то моя исходная позиция с N флагами – выигрышная. Однако, согласно нашему предположению, она проигрышная. Снова противоречие. Поэтому мы вынуждены признать, что наше исходное допущение о существовании неких плохих чисел, для которых теорема флагов неверна, ошибочно. Следовательно, плохих чисел нет и теорема верна для всех чисел. Итак, теорема флагов доказана.

Вы можете отреагировать на это доказательство двумя способами. Первый – восхититься системным парадом мыслей, который аккуратно провел нас по извилистому пути к неизбежному заключению. Второй (который, честно говоря, настолько же обоснован) – сказать: «Да зачем мы потратили на это две страницы? Я и так был в этом убежден! Я понимал, что вы подразумеваете под “и так далее…”, и не думал, что нужны еще какие-то объяснения. Неужели вы, математики, реально проводите целый день, соединяя продуманные аргументы, чтобы доказать то, что нормальный человек посчитал бы уже установленным вне всяких сомнений?»

Ну… иногда – да. Но не всегда. Как только вы увидите несколько подобных доказательств, вам больше не нужно их записывать. Вы видите «и так далее…» и считаете это доказательством не потому, что так оно и есть, а потому, что у вас достаточно опыта, чтобы понимать, что вместо многоточия можно написать строгое доказательство.

Игра «Ним» – это разновидность математики, или, если угодно, такая математика – это разновидность игры. Игру любят и охотно в нее играют по всему миру. Возникает вопрос: почему мы не обучаем ей в школе? Возможно, навыки игры в «Ним» не будут непосредственно связаны с вашей профессией (если вы не участник реалити-шоу), но если мы допускаем, что обучение математическому мышлению помогает нам лучше понимать все остальное[205], то такой анализ будет способствовать образованию. Нас постоянно ругают за то, что школьная система образования подавляет у учеников природное чувство игры. Если бы мы больше играли на уроках математики, стали бы школьники активнее ее изучать?

И да, и нет. Я преподаю математику больше двадцати лет. Когда я начинал, меня интересовали такие вопросы: как правильно учить математическим понятиям? Сначала примеры, а потом объяснение? Или сначала объяснение, а затем примеры? Дать возможность учащимся открыть принципы на основе приведенных мной примеров или написать на доске принципы и позволить ученикам самим подобрать примеры?

Я пришел к выводу, что единого правильного способа не существует. (Зато, вне сомнения, есть несколько неправильных.) Ученики разные, и нет универсального метода преподавания, который подошел бы всем. Должен признаться, что я не люблю игры. Я ненавижу проигрывать, поэтому они меня нервируют. Однажды я поссорился с мамой моего приятеля, когда она в карточной игре «Червы» добилась «выстрела по луне»[206]. Если бы план урока основывался на игре «Ним», он бы, вероятно, оттолкнул меня. Зато мог бы очаровать моего соседа по парте! Я думаю, что учителя математики должны применять все возможные методики преподавания и быстро их менять. Так вы повысите вероятность того, что каждый учащийся почувствует хотя бы иногда, что преподаватель после столь скучных неинтересных подробностей говорит о предмете в разумной манере.

Вы последовали моему совету и действительно сыграли в «Ним» 2  2? Это было не особо похоже на игру, верно? Когда вы знаете стратегию, это уже своего рода работа – как выполнение бессмысленного и чисто механического процесса. Вы правы. Он настолько механический, что его можно сделать таковым буквально. Вот американский патент (№ 2 215 544) 1940 года, а рядом «Ниматрон» во всей красе! Эта машина играет в «Ним», причем идеально. В электрическом духе того времени вместо камней использовались светящиеся лампочки. Через несколько лет один из ее изобретателей, физик Эдвард Кондон из компании Westinghouse Electric, присоединился к Манхэттенскому проекту, но ушел уже через шесть недель, жалуясь на «болезненно удручающую»[207] секретность.

Однако в 1940 году в Америке ее царил мир, и Кондон демонстрировал «Ниматрон» на Всемирной выставке в парке Флашинг-Медоуз в Нью-Йорке (раздел «Мир завтрашнего дня»). Тем летом «Ниматрон» сыграл на выставке в «Ним» сто тысяч партий. Газета The New York Times писала:

Что касается новинок, то компания Westinghouse[208] объявила о представлении «Ниматрона» – нового электрического робота 8 футов высотой, 3 фута шириной и массой 900 килограммов. «Ниматрон» противопоставит свой электрический мозг мыслительному аппарату человека и сыграет со всеми желающими в один из вариантов старинной китайской[209] игры под названием «Ним». В игре нужно выключать размещенные в четыре ряда лампочки, пока не погаснет последняя. «Ниматрон» обычно выигрывает, но если он проиграет, то противник получит жетон с надписью «Чемпион по “Ним”», обещают представители компании.

Но как человек мог победить, если «Ниматрон» играл идеально? Дело в том, что «Ниматрон» предлагал на выбор девять стартовых позиций, среди которых были выигрышные для человека, поэтому люди могли победить, если тоже играли идеально. Но обычно такого не случалось. По словам Кондона, большую часть поражений[210] автомат потерпел от операторов, которые демонстрировали публике, что его можно обыграть, поскольку люди после многочисленных попыток решали, что он непобедим.

В 1951 году британская электронная компания Ferranti построила собственного робота для игры в «Ним», назвав его Nimrod. Во время мирового турне он собирал толпы людей. В Лондоне группа экстрасенсов пыталась нарушить идеальную игру Nimrod с помощью концентрированных телепатических вибраций, но безуспешно. В Берлине машина сразилась с будущим канцлером Западной Германии Людвигом Эрхардом и обыграла его три раза подряд. Алан Тьюринг, работавший[211] над компьютером Ferranti Mark 1, заметил, что Nimrod настолько очаровал немецкую публику, что даже пустовал бесплатный бар в холле.

То, что компьютер может играть в «Ним» так же, как человек, казалось потрясающим (потрясающим вплоть до отказа немцев от пива!), но так ли это? Сам Тьюринг выразил определенный скептицизм, написав: «Читатель может спросить[212], почему мы используем эти сложные и дорогие машины для столь тривиального занятия, как игра». Конечно, игры играм рознь. Зная то, что нам сейчас известно о «Ним», мы понимаем: чтобы стать идеальным игроком, не нужно никакого человеческого мышления – достаточно всего лишь промаркировать дерево, шаг за шагом, от листьев до корня. Если вы играли в крестики-нолики, то, вероятно, наблюдали то же самое. Причина в том, что крестики-нолики тоже имеют геометрию дерева. Первые несколько шагов выглядят так[213]:

Однако есть разница: игра в крестики-нолики, в отличие от «Ним», может закончиться ничьей. На деле, если обоим игрокам больше семи лет, в основном так и происходит: большинство игр заканчиваются вничью.

Никаких проблем: это просто означает, что нам нужна буква Н для ничьей и три правила вместо двух.

ТРИ ПРАВИЛА

Первое правило: если каждый мой ход ведет в позицию В, то моя текущая позиция – П.

Второе правило: если я могу сделать ход, ведущий в позицию П, то моя текущая позиция – В.

Третье правило: если ни один мой ход не ведет в позицию П и не все мои ходы ведут в позицию В, то моя текущая позиция – Н.

Третье правило длиннее, но оно описывает, что значит находиться в ничейной позиции. Его первая часть говорит, что я не могу выиграть; согласно второй части, я не проиграл, потому что могу сделать какой-то ход, который не приведет противника к выигрышной позиции; а если ни я, ни он не можем друг друга обыграть, то это ничья.

Я прошу обратить внимание, что, независимо от того, какие варианты у нас есть в игре в крестики-нолики, мы всегда находимся в ситуации, когда применимо одно из трех правил, поэтому, как и в «Ним», можем добраться до корня игры – пустой доски, на которой оказывается буква Н.

Неудивительно, что никакой секретной стратегии для игры в крестики-нолики нет. Если оба игрока действуют идеально, неизменно получится ничья.

В математике так часто бывает. Вы сели решать одну задачу, а когда закончили (через день, месяц или год), понимаете, что одновременно решили еще несколько. Если у вас есть гвоздь и требуется изобрести для него молоток, то этим молотком можно будет забивать все, что похоже на гвоздь. Так происходит в большинстве случаев.

Крестики-нолики имеют геометрию дерева, поэтому три правила гарантируют, что игра закончится либо победой первого игрока, либо победой второго, либо ничьей. Более того, чисто механические расчеты могут нам сказать, какой из трех вариантов действительно реализуется и как выглядит идеальная стратегия.

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

1. У первого игрока есть стратегия, которая всегда гарантирует ему победу.

2. У второго игрока есть стратегия, которая всегда гарантирует ему победу.

3. Каждая безошибочно сыгранная игра заканчивается вничью.

Мы можем выяснить эти стратегии, маркируя дерево буквами В, П и Н в соответствии с тремя правилами от листьев к корню. Это может потребовать много времени, но результат будет гарантирован.

Многие игры – это деревья. Английские шашки – дерево. «Четыре в ряд» – дерево. Шахматы – дерево. Да, даже шахматы! Мы считаем их своего рода романтическим искусством, способом передать дух сражения на маленькой деревянной доске. Что-то в этом есть. О них сняты фильмы, написаны романы и даже мюзикл, созданный бывшими участниками группы ABBA.

И тем не менее это дерево. Игроки ходят по очереди, случайностей нет, а игра не может длиться дольше 5898 ходов. Этот теоретический максимум никогда не появится в партии, где игроки действительно стремятся выиграть. Самая длинная из когда-либо сыгранных турнирных игр[214] состояла из 269 ходов и заняла чуть больше 20 часов.

Если вы не разбираетесь в шахматах, то можете задаться вопросом, почему число ходов ограниченно. Это ведь не «Ним», вы не теряете пешку или фигуру с каждым ходом. Почему бы ладье и коню не гоняться друг за другом на доске вечно? Причина в том, что в шахматах установлены правила, запрещающие это. Если за 50 ходов не было взятий или ходов пешкой, то партия признается закончившейся вничью. Такие правила обусловлены той же логикой, которая заставляет нас исключить 1 из перечня простых чисел. Если бы 1 было простым числом, то процесс разложения на множители мог бы продолжаться бесконечно: 15 = 5  3  1  1  1… Это не совсем неверно, но совершенно бессмысленно. Правило 50 ходов не позволяет шахматам двигаться по тому же унылому вечному пути[215].

Так что шахматы, несмотря на все легенды и загадочность, по сути, то же самое, что крестики-нолики или «Ним». При встрече двух идеальных игроков либо белые всегда выигрывают, либо белые всегда проигрывают, либо неизменно будет ничья. И в принципе вычисление, какой из вариантов будет реализован, – всего лишь вопрос продвижения по дереву до корня. Шахматы – это сложная задача, но не настолько, как написание стихотворения, отражающего[216] пересечение политики атомного века середины столетия с модернизацией городов, ностальгией по детству, бесконечными отзвукам Гражданской войны и заменой человеческого духа механизированными изобретениями, а в смысле перемножения двух действительно больших чисел. Это может занять много времени, но в принципе вы знаете, как постепенно, шаг за шагом справиться с задачей.

В принципе. Это словосочетание – маленький коврик, элегантно уложенный над бездонной пропастью трудностей!

Игра «Ним» с двумя кучками по два камня – проигрыш. «Четыре в ряд»[217] – победа. Но для шахмат мы не знаем, будет победа, поражение или ничья. Возможно, никогда и не узнаем. У шахматного дерева очень много листьев. Нам доподлинно неизвестно сколько, но уж точно больше, чем способен рассмотреть восьмифутовый робот. Клод Шеннон, которого мы оставили за созданием фальшивого английского текста с помощью цепей Маркова, также написал одну из первых серьезных работ[218] о машинных шахматах; по его оценке, количество листьев на этом дереве выражается числом, примерно состоящим из единицы и 120 нулей, – сто миллионов триллионов гуголов. Это не просто большое число, оно больше, чем количество чего-либо во Вселенной, и уж точно это не то количество вещей, которые вам захочется просмотреть и обозначить буквами В, П или Н. В принципе, конечно, можно, но в реальности – нельзя.

Это явление (вычисления, которые мы умеем делать, но не делаем за неимением времени) – минорный мотив, звучащий на протяжении всей истории математики компьютерной эпохи. Вернемся на секунду к разложению на простые множители. Мы уже видели, что это можно делать без особых размышлений. Если вы начинаете, скажем, с числа 1001, то вам нужно найти число, на которое 1001 делится нацело, а если такого нет, то 1001 – простое число. Годится ли 2? Нет, 1001 не делится пополам. А 3? Нет. А 5? Нет. А 7? Да, поскольку 1001 = 7  143. (Тысяча и одна ночь – это сто сорок три недели.) Теперь можно махать топором над числом 143, проверяя деление за делением, пока не обнаружим, что 143 = 11  13.

Но что, если число, которое мы пытаемся разложить, состоит из двух сотен цифр? В этом случае проблема значительно превышает шахматный уровень. Чтобы проверить все возможные делители, не хватит продолжительности жизни Вселенной. Да, это всего лишь арифметика, но при этом, насколько нам известно, совершенно невыполнимая.

И это хорошо, поскольку в реальном мире, несомненно, есть нечто более ценное для вас, чья безопасность зависит от сложности этой задачи. Какое отношение факторизация чисел имеет к безопасности? Для этого нам нужно вернуться к криптографии конфедератов и книге экспериментальной поэзии в прозе Гертруды Стайн Tender Buttons («Нежные кнопки»).

Предположим, Акбар и Джефф после окончания игры решают тайно пообщаться. И это вполне реально, если у них есть общая секретная система кодирования. Общая – ключевое слово; они должны использовать один и тот же код, а это предполагает наличие некоторой общей информации, обычно называемой ключом. Допустим, ключом будет текст «Нежных кнопок» Гертруды Стайн. Если Акбар хочет втайне передать Джеффу сообщение Nim has grown dreary («Ним стал скучным»), он может сделать это так: написать его над первыми словами первого стихотворения в сборнике «Нежные кнопки» (A CARAFE, THAT IS A BLIND GLASS. A kind in glass and a cousin, a spectacle and nothing strange a single hurt color and an arrangement in a system to pointing), ставя в соответствие одну букву другой.

Теперь складываем каждую пару букв. Конечно, буквы не числа, но у каждой есть номер в алфавите, так что суммируем именно эти номера. Обычно начинают с 0, так что A – это буква номер 0, B – это буква номер 1 и так далее. В нашем случае в первой паре N – тринадцатая буква, A – нулевая, 13 + 0 = 13, поэтому берем тринадцатую букву N. Во второй паре сумма I + C дает 8 + 2 = 10, что соответствует десятой букве – K. Продолжая действовать таким образом, получаем в итоге зашифрованный текст NKM YAX K…

Однако дальше мы сталкиваемся с небольшой проблемой: R(17) + T(19) дает 36, а такой буквы нет. Но, оказывается, проблема легко решаема: после Z мы просто начинаем счет заново, и тогда двадцать шестая буква будет снова A, двадцать седьмая – B и так далее. Поэтому 36 будет соответствовать та же буква, что и числу 10, то есть K. В итоге ваше сообщение будет выглядеть так:

Теперь Джефф, получив зашифрованное сообщение и, разумеется, экземпляр книги Гертруды Стайн, может восстановить текст, но уже не добавляя, а вычитая буквы. N минус A означает 13 – 0 = 13, а числу 13 соответствует N. И так далее. Когда мы доберемся до второй K, нам предстоит вычесть T(19) из K(10). Получится – 9, но не беспокойтесь, все в порядке! Минус девятая буква находится за 9 букв до буквы А(0), а поскольку мы расположили буквы по циклу и A следует за Z, то девятая буква перед А – это восьмая буква перед Z, то есть R.

Если вам категорически не нравится сложение и вычитание, можете просто держать под рукой такую табличку[219]:

Она похожа на таблицу сложения, которой пользуются в начальной школе, но только для букв! Чтобы вычислить R + T, просто посмотрите на строку R и столбец T (или на строку T и столбец R) – и получите K.

Или еще лучше воспользоваться той геометрией, которую этот код накладывает на алфавит. По нашему правилу, когда мы сдвигаемся на одну букву правее Z, мы не выходим за пределы английского алфавита, а возвращаемся к А. Это означает, что мы представляем алфавит не в виде строки

ABCDEFGHIJKLMNOPQRSTUVWXYZ,

а в виде круга.

Каждая буква A в «Нежных кнопках» Гертруды Стайн – это 0; а значит, когда в ключе появляется А, мы оставляем букву исходного сообщения неизменной. Каждая буква С означает вращение круга против часовой стрелки на две позиции[220]. С такой геометрической точки зрения очевидно, почему этот код легко расшифровать при наличии ключа: достаточно повернуть круг на ту же величину, но по часовой стрелке.

Такой код называется шифром Виженера – в честь Блеза де Виженера, французского ученого XVI века, который его не изобретал. Подобные случаи в науке настолько распространены, что статистик и историк Стивен Стиглер сформулировал закон: «Ни одно научное открытие не названо в честь первооткрывателя». (Как отмечал сам Стиглер, закон Стиглера[221] впервые сформулировал социолог Роберт Мертон[222].)

Виженер был благородного происхождения[223], с хорошими связями, автором множества книг, секретарем у французского посланника на Вормсском рейхстаге, затем у герцога Неверского и короля Генриха. На таких должностях (особенно во время пребывания в Риме) он сталкивался с самыми сложными кодированными сообщениями. Мир римской криптографии XVI столетия был средоточием соперничества и ревностно охраняемых секретов. Известен случай, как Виженер разыграл одного из оппонентов, Пауло Панкатуччо, личного шифровальщика папы римского, написав ему сообщение по-детски примитивным шифром. Панкатуччо быстро декодировал текст и обнаружил поток оскорблений в свой адрес: «О бедный жалкий раб собственных дешифровок, на которые ты тратишь все свое масло и свои старания… Используй в будущем свой досуг и усилия на что-то более полезное и прекрати бездарно растрачивать свое время, одной-единственной минуты которого не купишь за все сокровища мира. Проверь прямо сейчас, сможешь ли ты узнать смысл хотя бы одной маленькой буквы из того, что написано дальше». И в этот момент шифр переключался на собственное изобретение Виженера – надежный код, который, как криптограф прекрасно знал, был Панкатуччо не по зубам. Все это нам известно из труда Виженера Traict des Chiffres ou Secrtes Manres d’Escrire («Трактат о цифрах и тайнописи»), который стал стандартным справочником по криптографии, в то время как остальные работы ученого были забыты. Трактат содержит множество собственных сложных кодов Виженера, а также основные идеи вышеописанного более простого шифра Виженера, на самом деле изложенные в 1553 году[224] в труде Джовани Беллазо, который его изобрел, работая секретарем и шифровальщиком у кардинала Дюранте Дюранти в Камерино. (Насколько высоко требовалось в те дни подняться в церковной иерархии, чтобы обзавестись собственным шифровальщиком?)

Беллазо был высокого мнения о своем шифре, утверждая, что он обладает «таким изумительным совершенством[225], что его может использовать весь мир, и при этом никто не сможет понять, что пишет другой, за исключением тех, кто обладает очень коротким ключом, как написано в этой книге вместе с объяснением и способом применения». Мир в целом согласился с его оценкой: так называемый шифр Виженера стал широко известен как le chiffre indechiffrable (неразгадываемый шифр). И действительно, до появления теста Касиски, который, как мог бы предсказать Стиглер, на самом деле был изобретен Чарльзом Бэббиджем за два десятилетия до Фридриха Касиски[226], надежных способов разгадать шифр Виженера не существовало[227]. Но даже этот метод не сработает, если ключ будет таким же длинным, как, например, «Нежные пуговицы» Гертруды Стайн.

Разумеется, шифр хорош лишь настолько, насколько добросовестны использующие его люди. К примеру, вы, вероятно, знаете, что Конфедерация (отколовшиеся южные штаты) вела войну против Соединенных Штатов в отчаянном стремлении сохранить чудовищную систему рабства; но знаете ли вы, что южане совершенно безобразно пользовались криптографией? Конфедераты использовали шифр Виженера с коротким ключом, повторяющимся во всем сообщении, и заботились только о кодировании слов, которые считали стратегически важными. Например, депеша, отправленная 30 сентября 1864 года Джефферсоном Дэвисом[228] генералу Эдмунду Кирби Смиту, гласила:

By which you may[229] effect O – TPQGEXYK – above that part HJ – OPG – KWMCT – patrolled by the ZMGRIK – GGIUL–CW – EWBNDLXL.

Шифровальщики конфедератов не только не зашифровали большую часть текста, но и сохранили длину зашифрованных слов. Поэтому неудивительно, что северяне, перехватив сообщение, догадались, что после слов above that part («выше той части») должно следовать выражение of the river («реки»). А имея фрагмент дешифрованного текста, определить ключ не проблема[230]. Вернитесь к алфавитному квадрату. Если слову OF соответствует слово HJ, то можно узнать буквы ключа. Буква O перешла в H, поэтому соответствующая буква в ключе будет T. Буква F перешла в J, поэтому должна быть E. На языке арифметики мы можем записать это так: H – O = T, а J – F = E. Действуя аналогичным образом и далее, получаем:

Из этой короткой фразы дешифровщик северян извлек уже больше половины использованного ключа конфедератов complete victory («Полная победа»), что выглядело несколько иронично, если учесть то, что вот-вот должно было случиться с южанами. А как только ключ известен, расшифровать оставшуюся часть сообщения – дело нескольких минут.

Если ключ длинный, то шифр Виженера более или менее сохраняет свой неразгадываемый статус. Однако тут есть проблема, причем серьезная. У кого-то еще, кроме Акбара и Джеффа, может быть экземпляр книги Гертруды Стайн «Нежные кнопки», и, соответственно, тогда этот кто-то с легкостью расшифрует их сообщения. Если Акбар или Джефф хотят включить в число доверенных собеседников Шебу[231], они должны послать ей экземпляр книги. При намерении отправить кому-то свой ключ вы не можете его зашифровать, поскольку у вашего адресата еще нет ключа для расшифровки; но если вы отправите его в незашифрованном виде и его перехватят, то тогда можно уже вообще не шифровать.

Это считалось одной из базовых проблем криптографии: ее нельзя было решить, а потому с ней приходилось мириться. В конце концов, Шеба и вражеский перехватчик находятся в одном и тот же положении: ни один из них не знает ключа. Вы не можете передать ключ Шебе, не отправив ей какого-то сообщения, но без ключа вы не можете защитить это сообщение от вражеских глаз. Как отослать сообщение так, чтобы Шеба могла его прочитать, а враг – нет? И вот тут – совершенно внезапно и чудесно, как доставка цветов от нового интересного знакомого, – на пороге появляется разложение простых чисел на множители.

Оказывается, умножение больших чисел – это то, что математики называют односторонней функцией с потайным входом. Потайной вход – это дверь, в которую легко войти, но очень сложно выйти. Умножение двух чисел из тысячи цифр – действие, которое ваш смартфон выполнит так быстро, что вы и глазом не успеете моргнуть. Разложить это произведение на два исходных сомножителя – задача, которую ни один известный алгоритм не сможет решить за миллион миллионов человеческих жизней. И эту асимметрию вы можете использовать для передачи ключа Шебе так, чтобы противник ничего не мог с этим поделать. А поможет в этом замечательный алгоритм RSA, названный так в честь Рональда Ривеста, Ади Шамира и Леонарда Адлемана (Rivest, Shamir, Adleman), которые изобрели его в 1977 году. По крайней мере они были теми, кто его изобрел и рассказал всем об этом. Реальная история несколько интереснее. В полном соответствии с законом Стиглера система RSA носит имя не тех, кто ее создал. На самом деле она была изобретена в начале 1970-х Клиффордом Коксом и Джеймсом Эллисом. Но на этот раз для изменения авторства была крайне веская причина: Кокс и Эллис работали в Центре правительственной связи – сверхсекретной спецслужбе Великобритании. До 1990-х никто[232], кроме узкого круга лиц, не должен был знать, что алгоритм RSA был раньше, чем работа R, S и A.

Детали алгоритма RSA содержат несколько больше теории чисел, чем я хотел бы здесь поместить, но вот ключевая вещь. Шеба знает два очень больших простых числа, p и q. Никто, кроме нее, их не знает – ни Акбар, ни Джефф, ни кто-либо еще. Эти числа – ключи. Алгоритм RSA для декодирования сообщения может быть использован любым, кто знает эти два больших простых числа.

Однако для шифрования сообщений вам нужно знать не числа p и q, а только их произведение – огромное число, которое мы обозначим N. Так что это вовсе не похоже на шифр Виженера, где расшифровка – это просто процесс шифрования, выполняемый в обратном порядке с применением того же ключа. В системе RSA шифрование и расшифровывание – совершенно разные процедуры, причем первая благодаря потайному входу намного проще второй.

Это большое число N называется открытым ключом, поскольку Шеба может сообщить его всем, а при желании даже прилепить его на входную дверь своего дома. Акбару, чтобы отправить Шебе сообщение, нужно знать только произведение N; с его помощью он может зашифровать свое сообщение, а Шеба с помощью чисел p и q превратит его обратно в исходный текст. Любой человек может с помощью числа N присылать Шебе сообщения, их можно даже открыто публиковать. Увидеть их смогут все, а вот прочитать – только Шеба, обладательница тайных ключей.

С появлением криптографии с открытым ключом все существенно упростилось. Вы (или ваш компьютер, телефон или холодильник) можете отправлять сообщения множеству людей одновременно, не опасаясь утечки конфиденциальной информации. Но тут все держится на надежности потайного входа. Если кто-то построит под ним лестницу, блегчив путь в обе стороны, все сооружение рухнет. Иными словами, если бы кто-то изобрел способ разложить число N на составляющие простые множители p и q, то мгновенно получил бы доступ ко всем ранее отправленным личным сообщениям, зашифрованным с помощью числа N.

Если проблема разложения числа на простые множители, как и проблема выигрыша в шахматной партии, окажется для какой-нибудь компьютерной программы более простой задачей, чем мы думали, то передача информации внезапно станет гораздо более опасным занятием. Вот почему вы видите романы-триллеры, как я недавно в аэропорту[233], с таким текстом на задней обложке:

Подросток Берни Вебер[234] – математический гений. Вашингтон, ЦРУ и Йельский университет внедряются в Милуоки, чтобы похитить его. Они хотят узнать его секрет разложения простых чисел.

(Если вы не засмеялись над последним предложением, остановитесь и хорошенько подумайте над математической задачей, с которой, как предполагается, справился Берни.)

Программа «Чинук» играла в шашки лучше кого-либо из ныне живущих или живших на земле. Однако это не означало, что победить ее нельзя было в принципе. Возможно, где-то в глубинах дерева шашек скрывалась какая-то превосходная стратегия, неизвестная человеку и машине, которая могла привести к чемпионству. Единственный способ полностью это исключить – проанализировать шашки до самого конца, чтобы узнать, какой буквой обозначить корень дерева. К какому из трех типов игры относятся английские шашки? Всегда побеждает первый игрок? Второй? Ничья?

Давайте я не стану испытывать ваше терпение. Будет ничья. С математической точки зрения шашки – это более или менее масштабная двухцветная версия крестиков-ноликов. Два игрока, которые никогда не ошибаются, не выиграют и не проиграют, всегда сыграют вничью. Возможно, это не станет большим сюрпризом для последователей Мариона Тинсли, который, как вы помните, ошибался крайне редко. Его конкуренты тоже ошибались ненамного чаще. И когда два таких почти идеальных игрока встречались за доской, партии в основном заканчивались вничью. В 1863 году Джеймс Уилли, шотландский чемпион по прозвищу Пастушок[235], встретился в Глазго в матче за звание чемпиона мира с Робертом Мартинсом из Корнуолла. Они сыграли пятьдесят партий, и все вничью. Причем двадцать восемь[236] были совершенно одинаковыми – ход в ход. Скукотища! Такая ситуация вынудила ввести в английских шашках систему ограничений: теперь первые два хода выбирались наугад из набора разрешенных дебютов, что уменьшало вероятность хождения игроками по одним и тем же проторенным дорожкам дерева, поднимаясь к одному и тому же листу. Однако после того, как в 1928 году Сэмюэл Гоноцкий и Майк Либер[237] сыграли сорок ничьих подряд в матче на ставку в 1000 долларов в отеле Garden City на Лонг-Айленде в Нью-Йорке, пришлось перейти к нынешнему ограничению с жеребьевкой первых трех ходов, которые выбираются из 156 вариантов с названиями вроде «Ужасный Эдинбург», «Хендерсон», «Глушь», «Ад Фрейзера» или «Твистер Оливера»[238]. Но даже с такой жеребьевкой количество ничьих в современных турнирах по английским шашкам значительно больше, чем побед или поражений[239].

Однако это всего лишь куча эмпирических свидетельств; совсем другое дело – строгое доказательство того, что ни у одного из игроков нет выигрышной стратегии, которую каким-то образом умудрились упустить целые поколения мастеров шашек.

Программе «Чинук» было всего пять лет, когда она отобрала шашечную корону у Мариона Тинсли в 1994 году. Пройдет еще тринадцать лет, прежде чем Джонатан Шеффер и его команда докажут, что Тинсли не может обыграть «Чинук». И никто другой не может. И уж точно не вы.

Хотя можете попробовать! «Чинук» трудится день и ночь на своем сервере в Эдмонтоне (провинция Альберта), встречаясь со всеми желающими. По ходу игры он спокойно оценивает свою позицию. «У “Чинука” есть небольшое преимущество», – сообщает он. Затем: «У “Чинука” большое преимущество». А через семь ходов в той партии, которую я играю, пока пишу эти строки: «Вы проигрываете». Это означает, что вы достигли позиции, которую программа со своей всеобъемлющей точки зрения обозначает буквой В. Это не значит, что вы должны прекратить играть! Машина терпелива. Куда ей деваться? Можете сделать еще ход. «Чинук» двигает свою шашку и снова предупреждает: «Вы проигрываете». Продолжайте, пока хватит выдержки.

Игра против «Чинука» расстраивает, но в то же время успокаивает. Это сильно отличается от игры против очень-очень умелого человека, который стремится вас обыграть: вас игра расстраивает, но не успокаивает. Как-то я играл в го со своим пятнадцатилетним кузеном Закари, который тогда был ударником в группе Sinister Mustard, игравшей треш-метал, и одним из лучших молодых шахматистов Аризоны. До этого Закари никогда не играл в го, и поначалу я получил изрядное преимущество. Но примерно на четверти партии что-то у него щелкнуло: он уловил логику игры, как намного ранее уловил логику шахмат, и энергично стер меня со стола. Говорили, что игра против Тинсли была во многом примерно такой же: неизменно вежливого и мягкого профессора математики называли Ужасный Тинсли – просто потому, что сесть с ним за доску означало, что вас почти гарантированно снесут бульдозером. И Тинсли, и версия «Чинука» 1994 года были практически идеальными игроками в шашки. Но, в отличие от «Чинука», Мариона заботило, выиграет ли он. «В целом я неуверенный в себе человек[240], – признался он в одном из интервью, – и ненавижу проигрывать». По мнению Тинсли, они с «Чинуком» принципиально разные, хотя и выполняли одну и ту же задачу. Перед состязанием в 1992 году он сказал репортеру одной газеты: «Мой программист лучше[241], чем у “Чинука”. У него был Джонатан, а у меня – Господь Бог».

В английских шашках есть 500 995 484 682 338 672 639 возможных позиций (согласно Шефферу), хотя в легальной партии многих из них достичь нельзя. Поскольку шашки – это дерево[242], мы можем двигаться в обратном направлении от конца игры, присваивая каждой позиции букву В, П или Н.

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

Самый популярный из первых семи возможных ходов в английских шашках обозначается[243] 11–15, но опытные игроки настолько горячо его любят, что обычно называют «старый добрый». Предположим, что черные начинают со «старого доброго», а белые отвечают 22–18 (это начало дебюта под названием «Двойной угол 26–17»). Теперь ход черных. В этот момент Шеффер доказывает, что для черных эта позиция – либо П, либо Н, но они точно не могут форсированно выиграть. Поэтому обозначим это положение ПН, чтобы показать, что пока еще не закончили для него вычисления.

Однако это уже может кое-что сказать о ходе «старый добрый»! Согласно трем правилам, позиция обозначается П только в том случае, если каждая позиция, куда можно из нее перейти, будет В. Однако для «старого доброго» это неверно, потому что у белых есть ход 22–18, ведущий либо к П, либо к Н. Следовательно, мы знаем, что «старый добрый» – это либо Н, либо В. И знаем мы это, не утруждая себя изучением любого из множества других возможных ответов на «старый добрый», имеющихся в распоряжении белых, или точным определением буквы, которую надо присвоить позиции после 22–18. Выражаясь языком информатики или лесоводства, мы обрезаем те ветви, от которых можно избавиться, не рассматривая. Это чрезвычайно важный прием. Часто люди думают, что достижения вычислительной техники обусловлены тем, что мы делаем наши компьютеры невероятно быстрыми, чтобы они могли обрабатывать больше данных. Однако не менее важно обрезать большие объемы данных, не имеющие отношения к рассматриваемой задаче! Самое быстрое вычисление – то, которое вы не выполняете.

На самом деле можно продемонстрировать, что все семь открывающих ходов ведут либо к Н, либо к В. Только для одного из них, 9–13, Шефферу нужно копнуть глубже и показать, что это Н.

И этого достаточно, чтобы полностью решить шашки! Мы знаем, что черные, начиная игру, имеют ход, а именно 9–13, который не дает белым выигрышной позиции. Следовательно, начальная позиция не может быть П. Но мы также знаем, что ни один из возможных ходов черных не дает белым позицию П, а потому исходная позиция не может быть В. Остается один вариант: исходная позиция – Н, и шашки – ничейная игра.

Для шахмат такого анализа нет. Возможно, пока. А может, не будет никогда. Дерево шахмат – это секвойя по сравнению с кустиком шашек, и мы не знаем, какая буква будет у корня – В, П или Н.

А если бы знали? Станут ли люди посвящать жизнь шахматам, зная, что при идеальной игре партия неизменно завершится ничьей, что нельзя выиграть благодаря блестящей логике, а можно только проиграть из-за оплошности? Или они ощутят опустошенность? Ли Седоль, один из лучших в истории игроков в го, прекратил играть в турнирах после поражения в матче с AlphaGo – программой, разработанной компанией DeepMind. «Даже если я буду номером один[244], – объяснил он, – есть сущность, которую нельзя победить». А ведь игра го еще полностью не решена! По сравнению с секвойей, изображающей шахматы, го – это… ну, вот если бы существовало дерево размером больше, чем гугол секвой, то го была бы именно им. Почитайте форумы, посвященные шахматам и го, и увидите, сколько людей высказывают те же опасения, что и Ли Седоль. Если игра – это всего лишь дерево с написанными на нем буквами, то действительно ли это все еще игра? Может, нам стоит просто уйти, когда «Чинук» со спокойствием и бесконечным терпением сообщает, что мы проиграли?

Международный зал славы английских шашек был когда-то главной достопримечательностью Петала (штат Миссисипи) – города с населением десять тысяч человек, расположенного недалеко от университетского городка в Хаттисберге. В здании площадью свыше 3000 квадратных метров был установлен бюст Мариона Тинсли, самая большая шашечная доска в мире, а также вторая по величине шашечная доска в мире. Зал закрылся в 2006 году[245] после того, как его основателя приговорили к пяти годам тюрьмы за отмывание денег. В 2007 году (том самом, когда Шеффер доказал, что шашки – ничейная игра) здание сгорело дотла.

И тем не менее люди по-прежнему повсеместно играют в шашки и продолжают бороться за звание чемпиона мира среди людей. (На момент написания этих слов титул принадлежал итальянскому шашисту Серджо Скарпетте.) Конечно, шашки уже не так популярны, как раньше, но спад начался задолго до появления доказательства Шеффера, а новые игроки всё продолжают пополнять ряды шашистов. Одной из лучших шашисток мира Амангуль Бердыевой из Туркменистана было семь лет, когда программа «Чинук» отобрала корону у Тинсли. Нынешний чемпион мира в классической версии (без жеребьевки первых ходов), 49-летний Лубабало Кондло из Южной Африки, разработал свой вариант того самого дебюта, в котором Уилли и Мартинс сыграли сорок раз вничью в Шотландии в 1863 году; вариант Кондло в честь того матча сейчас известен как «Африканский Глазго».

Если цель игры в шашки – выигрывать лучше всех, то больше нет смысла в них играть. К счастью, смысл игры не в этом. Никто из людей не играл лучше Тинсли, и Тинсли знал, что суть не в победе. «Конечно, я очень не люблю проигрывать[246], – признался он в интервью в 1985 году, – но если мы сыграем много красивых партий, это будет моей наградой. Шашки – такая красивая игра, что я даже не против проиграть». Шахматы ничем не отличаются. Нынешний чемпион мира Магнус Карлсен сказал: «Я не считаю компьютеры противниками[247]. Для меня интереснее обыгрывать людей». Гарри Каспаров, долгие годы удерживавший звание чемпиона мира, отвергает идею, что человеческие шахматы[248] устарели, поскольку для него игра людей и вычисления компьютера – принципиально разные вещи. По его мнению, человеческие шахматы – это форма психологической войны. Это не дерево, а сражение на дереве. Вспоминая партию, сыгранную против Веселина Топалова двадцать лет назад, Каспаров объясняет: «Я был поражен[249] красотой этой геометрии». Геометрия дерева говорит вам, как выиграть, но ничего не говорит о том, что делает игру красивой. Это более тонкая геометрия, и на данный момент ни одна машина не может рассчитать ее шаг за шагом с помощью какого-то короткого списка правил.

Совершенство – это не красота. У нас есть абсолютное доказательство того, что идеальные игроки не выигрывают и не проигрывают. Любой наш интерес к игре существует именно потому, что люди несовершенны. И возможно, это неплохо. Идеальная игра – это вовсе и не игра в прямом смысле слова. Наше личное присутствие в игре происходит в силу нашего несовершенства. Мы что-то чувствуем, когда наши недостатки сталкиваются с недостатками других людей.