Форма реальности. Скрытая геометрия стратегии, информации, общества, биологии и всего остального

ДВА ПРАВИЛА

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

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

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

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

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

Метод дерева работает для игры «Ним» с большим количеством кучек и камней, то есть для всех вариантов игры. Хотите знать, кто выиграет с двумя кучками по 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], которые настолько жизнестойки, что могут выдержать путешествие в космос на метеорите и колонизировать новую планету после удара. Доказательство позволяет мыслям перемещаться. Считается, что мы, математики, стоим на плечах гигантов, но я предпочитаю говорить, что мы идем по лестнице застывших мыслей обычных людей. Мы добираемся до вершины, окропляем своими мыслями лед, они примерзают к нему и делают лестницу еще выше. Может, это не столь выразительно, зато гораздо правдивее.