Текст книги "Форма реальности"

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

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

В варианте игры «Ним» под названием «Игра с вычитанием» вы начинаете с одной кучи камней и вам разрешается взять только 1, 2 или 3 камня. Побеждает игрок, взявший последний камень. Эта игра тоже представляет собой дерево, и вы можете аналогичным образом проанализировать ее, начиная с конца. Эта версия «Ним» получила известность благодаря появлению в качестве задания для участников пятого сезона реалити-шоу Survivor («Последний герой»), который снимался в Таиланде. (Там игру назвали не «Ним» и не «Игра с вычитанием», а «Тай 21», хотя у нее нет тайских корней; возможно, такое название ориентировано на американскую аудиторию, которая склонна считать вещи азиатского происхождения мудреными и непостижимыми.) По той же причине сохраняется неискоренимая традиция описывать «Ним» как древнюю китайскую игру, хотя это, видимо, полностью вымышлено: впервые она упоминается[200]200
  Впервые она упоминается: L. Rougetet, “A Prehistory of Nim,” College Mathematics Journal 45, no. 5 (2014): 358–363.


[Закрыть] в книге математических головоломок и фокусов Луки Бартоломео де Пачоли, который был другом Леонардо да Винчи, францисканским монахом и общепризнанным «отцом двойной бухгалтерии». (Неужели это менее интересно, чем происхождение из Древнего Китая?)

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


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

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

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

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


[Закрыть].

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

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

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

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

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

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

Доказательство – это кристаллизованная мысль. Оно берет блестящий радостный момент «понимания» и фиксирует его на странице, чтобы мы могли поразмышлять над ним на досуге. Что еще важнее, мы можем поделиться доказательством с другими людьми, в чьем сознании оно снова оживает, словно одна из тех выносливых микробных спор[203]203
  Одну из тех выносливых микробных спор: W. Fajardo-Cavazos et al., “Bacillus Subtilis Spores on Artificial Meteorites Survive Hypervelocity Atmospheric Entry: Implications for Lithopanspermia,” Astrobiology 5, no. 6 (Dec. 2005): 726–36; www.ncbi.nlm.nih.gov/pubmed/16379527.


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

И ТАК ДАЛЕЕ…

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

Теорема флагов: если количество флагов равно 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]204
  На языке теории чисел можно сказать, что вам нужно взять остаток от деления текущего числа флагов на 4.


[Закрыть]. Теперь, согласно ТФ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]205
  И раз уж вы оказались здесь – довольно далеко в этой книге, то я полагаю, что мы это допустили?


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

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

Я пришел к выводу, что единого правильного способа не существует. (Зато, вне сомнения, есть несколько неправильных.) Ученики разные, и нет универсального метода преподавания, который подошел бы всем. Должен признаться, что я не люблю игры. Я ненавижу проигрывать, поэтому они меня нервируют. Однажды я поссорился с мамой моего приятеля, когда она в карточной игре «Червы» добилась «выстрела по луне»[206]206
  «Выстрел по луне» (shooting the moon) – ситуация в «Червах», когда игрок собирает все очковые карты за раунд и получает 0 очков, а все противники получают по 26 очков. Поскольку цель игры – набрать минимум очков, то игрок, «выстреливший по луне», получает большое преимущество. Прим. пер.


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

МИР «НИМАТРОНА»

Вы последовали моему совету и действительно сыграли в «Ним» 2 × 2? Это было не особо похоже на игру, верно? Когда вы знаете стратегию, это уже своего рода работа – как выполнение бессмысленного и чисто механического процесса. Вы правы. Он настолько механический, что его можно сделать таковым буквально. Вот американский патент (№ 2 215 544) 1940 года, а рядом «Ниматрон» во всей красе! Эта машина играет в «Ним», причем идеально. В электрическом духе того времени вместо камней использовались светящиеся лампочки. Через несколько лет один из ее изобретателей, физик Эдвард Кондон из компании Westinghouse Electric, присоединился к Манхэттенскому проекту, но ушел уже через шесть недель, жалуясь на «болезненно удручающую»[207]207
  Болезненно удручающую: Jessica Wang, “Science, Security, and the Cold War: The Case of E. U. Condon,” Isis 83, no. 2 (1992): 243.


[Закрыть] секретность.

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

Что касается новинок, то компания Westinghouse[208]208
  Что касается новинок, то компания Westinghouse: “Fair’s Ticket Sale Is ‘Huge Success,’ with Late Rush On,” New York Times, May 6, 1940, 9. После материала о «Ниматроне» идет объявление, что на ярмарке в специальном стеклянном будуаре будет показана Элси, «корова-звезда завтрашнего молочного мира компании Borden».


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


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

Но как человек мог победить, если «Ниматрон» играл идеально? Дело в том, что «Ниматрон» предлагал на выбор девять стартовых позиций, среди которых были выигрышные для человека, поэтому люди могли победить, если тоже играли идеально. Но обычно такого не случалось. По словам Кондона, большую часть поражений[210]210
  Большую часть поражений: E. U. Condon, “The Nimatron,” American Mathematical Monthly 49, no. 5 (1942): 331.


[Закрыть] автомат потерпел от операторов, которые демонстрировали публике, что его можно обыграть, поскольку люди после многочисленных попыток решали, что он непобедим.

В 1951 году британская электронная компания Ferranti построила собственного робота для игры в «Ним», назвав его Nimrod. Во время мирового турне он собирал толпы людей. В Лондоне группа экстрасенсов пыталась нарушить идеальную игру Nimrod с помощью концентрированных телепатических вибраций, но безуспешно. В Берлине машина сразилась с будущим канцлером Западной Германии Людвигом Эрхардом и обыграла его три раза подряд. Алан Тьюринг, работавший[211]211
  Алан Тьюринг, работавший: S. Barry Cooper and J. Van Leeuwen, Alan Turing (Amsterdam: Elsevier Science & Technology, 2013), 626.


[Закрыть] над компьютером Ferranti Mark 1, заметил, что Nimrod настолько очаровал немецкую публику, что даже пустовал бесплатный бар в холле.

То, что компьютер может играть в «Ним» так же, как человек, казалось потрясающим (потрясающим вплоть до отказа немцев от пива!), но так ли это? Сам Тьюринг выразил определенный скептицизм, написав: «Читатель может спросить[212]212
  Читатель вполне может спросить: Cooper and Van Leeuwen, Alan Turing.


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


[Закрыть]:

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

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

ТРИ ПРАВИЛА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И тем не менее это дерево. Игроки ходят по очереди, случайностей нет, а игра не может длиться дольше 5898 ходов. Этот теоретический максимум никогда не появится в партии, где игроки действительно стремятся выиграть. Самая длинная из когда-либо сыгранных турнирных игр[214]214
  Самая длинная из когда-либо сыгранных турнирных игр: о самой длинной теоретически возможной партии ведутся споры, но чаще всего звучит число 5898. В 1989 году в Белграде Иван Николич и Горан Арсович сыграли партию из 269 ходов. В обычной шахматной нотации ход включает по одному движению фигур каждого из игроков, так что путь на дереве, соответствующий этой партии, в реальности состоит из 538 отрезков.


[Закрыть] состояла из 269 ходов и заняла чуть больше 20 часов.

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


[Закрыть].

Так что шахматы, несмотря на все легенды и загадочность, по сути, то же самое, что крестики-нолики или «Ним». При встрече двух идеальных игроков либо белые всегда выигрывают, либо белые всегда проигрывают, либо неизменно будет ничья. И в принципе вычисление, какой из вариантов будет реализован, – всего лишь вопрос продвижения по дереву до корня. Шахматы – это сложная задача, но не настолько, как написание стихотворения, отражающего[216]216
  Написания стихотворения, отражающего: Robert Lowell, “For the Union Dead” (1960), из его книги 1964 года с тем же названием. Вы можете прочитать это стихотворение на сайте: https://www.poetryfoundation.org/poems/57035/for-the-union-dead.


[Закрыть] пересечение политики атомного века середины столетия с модернизацией городов, ностальгией по детству, бесконечными отзвуками Гражданской войны и заменой человеческого духа механизированными изобретениями, а в смысле перемножения двух действительно больших чисел. Это может занять много времени, но в принципе вы знаете, как постепенно, шаг за шагом справиться с задачей.

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

Игра «Ним» с двумя кучками по два камня – проигрыш. «Четыре в ряд»[217]217
  Четыре в ряд: этот факт почти одновременно доказали в 1888 году Джеймс Аллен и Виктор Эллис. Смотрите магистерскую работу Эллиса. Victor Allis. 1988. “A Knowledge-based Approach of Connect-Four – The Game is Solved: White Wins.” Masters thesis. Vrije Universiteit, Amsterdam.


[Закрыть] – победа. Но для шахмат мы не знаем, будет победа, поражение или ничья. Возможно, никогда и не узнаем. У шахматного дерева очень много листьев. Нам доподлинно неизвестно сколько, но уж точно больше, чем способен рассмотреть восьмифутовый робот. Клод Шеннон, которого мы оставили за созданием фальшивого английского текста с помощью цепей Маркова, также написал одну из первых серьезных работ[218]218
  Одну из первых серьезных работ: Claude E. Shannon, “XXII. Programming a Computer for Playing Chess,” London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 41, no. 314 (1950): 256–75.


[Закрыть] о машинных шахматах; по его оценке, количество листьев на этом дереве выражается числом, примерно состоящим из единицы и 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]219
  Можете просто держать под рукой такую табличку: иллюстрация из статьи C. J. Mendelsohn, “Blaise de Vigenère and the Chiffre Carré,” Proceedings of the American Philosophical Society 82, no. 2 (Mar. 22, 1940): 107.


[Закрыть]:

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

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ,

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

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


[Закрыть]. С такой геометрической точки зрения очевидно, почему этот код легко расшифровать при наличии ключа: достаточно повернуть круг на ту же величину, но по часовой стрелке.