А если есть всего один камень? Тогда у меня только один вариант. Я беру камень и выигрываю. Поэтому я пишу букву В над каждой такой позицией.
Как насчет двух камней в одной куче? Теперь ситуация усложняется, поскольку у меня есть выбор. Я могу взять оба камня и, сделав это, выиграю. Но если я глуп, невнимателен, извращен или, наоборот, великодушен и беру всего один камень, то я оставляю противнику выигрышную позицию, которую мы только что обозначили буквой В, и проигрываю. Какой буквой нужно обозначить позицию, где все зависит от моих действий? Будем исходить из того, что игроки в конкурентных играх не отличаются глупостью, невнимательностью, извращенностью или великодушием, а хотят победить и всегда выбирают тот ход, который ведет к победе. Поэтому обозначим такую позицию В. Уточняю: это вовсе не значит, что я выиграю, что бы я ни делал дальше. В большинстве игр это вовсе не так: какой бы хорошей ни была ваша позиция, всегда есть риск сделать неудачный ход. Буква В просто означает, что один из имеющихся у меня ходов ставит моего противника в проигрышную позицию. Вы можете рассматривать это как «путь к победе».
Две кучки по одному камню – совершенно другое дело. Что бы я ни делал, я ставлю соперника в позицию В, обеспечивающую ему выигрыш. Следовательно, ее нужно подписать буквой П.
Вот так на данный момент выглядит наше дерево.
Теперь можем продолжить, двигаясь назад во времени шаг за шагом. Две кучки, в одной два камня, а в другой один? У нас есть три варианта хода: убрать меньшую кучку, убрать большую кучку или взять из нее один камень. Получающиеся позиции уже обозначены В, В, П. Но поскольку один из ходов означает проигрыш моего противника, мне следует выбрать именно его, и данная позиция получает букву В. Игрок, которому осталась позиция с двумя кучками или одной, выигрывает, если сделает верный ход.
Вы выигрываете, когда ваш противник вынужден проиграть. Звучит как мотивационный плакат в спортзале, но на самом деле это математика. На языке деревьев это означает следующее: «Обозначайте позицию буквой В, если в ней существует ветвь, ведущая в позицию П». По тем же соображениям обозначайте позицию буквой П, если это не так. Ведь это означает, что при любом выборе вы оставляете оппоненту позицию В. Вы проигрываете, когда ваш оппонент может победить, что бы вы ни делали.
Все сводится к следующему.
Первое правило. Если каждый мой ход ведет в позицию В, то моя текущая позиция – П.
Второе правило. Если какой-то сделанный мной ход приведет в позицию П, то моя текущая позиция – В.
Эти два правила позволяют нам системно маркировать любое положение буквами П или В – вплоть до корня, с которого мы начинали игру. При этом мы никогда не зациклимся, потому что у деревьев нет циклов.
Корень обозначен буквой П, поэтому начинающий игру Акбар проигрывает, если, конечно, Джефф не сделает неправильного хода.
Я могу описать этот процесс словами, но стоит ли? Чтобы досконально с ним разобраться, нужно поиграть самому. Позовите друга, предложите поиграть в «Ним» с двумя кучками по два камня. Пусть ваш друг ходит первым (поскольку вы, возможно, не такой уж и хороший друг). А теперь используйте нарисованное выше дерево для выбора ходов. Выигрывайте, выигрывайте и выигрывайте. Так вы прочувствуете, как это работает.
Метод дерева работает для игры «Ним» с большим количеством кучек и камней, то есть для всех вариантов игры. Хотите знать, кто выиграет с двумя кучками по 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].
Запоздалое озарение их не спасло, но оно все еще полезно для нас. Почему невыгодно оставаться с четырьмя флагами? Потому что на каждый ваш ход противник дает естественный ответ. Вы берете два, и они два. Вы один, они – три. Вы три, они – один. Во всех случаях все четыре флага разобраны, игра окончена, победитель не вы.