Помоги проекту - поделись книгой:
Игры и занимательная математика непрерывно развивались в течение XIX и начала XX веков, и спектр задач неуклонно расширялся. Среди авторов XIX века следует упомянуть Джеймса Джозефа Сильвестра (1814—1897), Льюиса Кэрролла (1832—1898), Эдуарда Люка (1842—1891) и Уильяма Роуза Болла (1850—1925). Рассказать обо всех подробно просто невозможно, и далее мы остановимся на книгах Кэрролла и Люка.
Преподобный Чарльз Латуидж Доджсон, известный как Льюис Кэрролл, автор сказок об Алисе, был математиком и профессором Оксфорда. Он обожал занимательную математику и планировал издать серию книг под названием Curiosa Mathematica («Математические курьезы»). Завершить этот труд ему не удалось. Во второй книге этой серии под названием «Полуночные задачи, придуманные в часы бессонницы» он демонстрирует выдающиеся способности, приводя решения как простейших и шутливых («Есть двое часов. Одни стоят, другие опаздывают на одну минуту. Какие часы показывают время точнее?»), так и довольно сложных задач («Даны три произвольные точки на бесконечной плоскости. Какова вероятность того, что они образуют тупоугольный треугольник?»).
Кэрролл был не только гениальным автором математических и логических игр, но и великим знатоком английского языка, что можно увидеть в его книгах об Алисе и в многочисленных придуманных им играх со словами. Одна из них, «Лестница слов», заключается в том, что нужно построить цепочку из слов с одинаковым количеством букв, каждый раз меняя по одной букве в слове. Например, можно превратить козу в волка: КОЗА — ПОЗА — ПОЛА — ПОЛК — ВОЛК.
Наиболее значимая роль в развитии математических игр принадлежит французскому математику Эдуарду Люка, специалисту по теории чисел и в особенности по числам Фибоначчи. Он является автором великолепного сборника Recreations mathematiques («Математические развлечения»). Эта книга содержит 35 разделов, посвященных математическому анализу игр и занимательным задачам. Среди игр, придуманных Люка, выделяются «Ханойские башни». Сам Люка, чтобы создать завесу тайны, на презентации игры в 1883 году приписал ее авторство китайскому профессору Клаусу (Claus) из колледжа Ли-Су-Стьян (Li Sou Stain). Обратите внимание, что имя несуществующего профессора — анаграмма фамилии самого Люка (Lucas), а название колледжа — анаграмма колледжа Сен-Луи (Saint Louis), где Люка преподавал математику.
Одна из последних книг XIX века по занимательной математике — Mathematical Recreations and Essays («Математические эссе и развлечения», 1892) Уолтера Роуза Болла, которая в XX веке стала одной из популярнейших книг по этой теме, выдержав более 12 изданий. Редактором одного из изданий в 1938 году выступил геометр Гарольд Коксетер.
Одна из игр, о которых пишет Эдуард Люка в третьем томе своей книги о занимательной математике, принадлежит к типу игр, в которых нужно окружить своими фишками фишки другого игрока. К таким играм относятся «Охота на зайца» из книги Альфонсо X Мудрого и «Лиса и гуси» — очень популярная в викторианской Англии игра, известная еще с XV века.
В «военных играх» отсутствует элемент случайности. Эта игра рассчитана на двух игроков и была очень популярной среди французских военных в XIX веке. У одного игрока три белых фишки, у другого (ему принадлежит первый ход) — одна черная фишка. Фишки располагаются на доске из 11 клеток (начальное положение фишек показано на рисунке ниже). Задача белых фишек — окружить черную, которая пытается сбежать. Фишки могут перемещаться по пустым клеткам вдоль линий игрового поля, но белые фишки не могут отступать, в то время как черная может двигаться в любом направлении.
Игра кажется простой, и при первом знакомстве может показаться, что черной фишке легко скрыться от белых. Но тщательный анализ, проведенный Эдуардом Люка, показывает, что существует выигрышная стратегия для белых фишек — у них всегда есть в запасе минимум один ход, который мешает черной фишке сбежать. После изучения вариантов развития игры становится ясно, что максимальное число ходов равно 12, и количество существенно различных игр сокращается до 16. Кажется невероятным, что эта небольшая игра требует такой выверенности ходов от играющего белыми фишками. Он всегда будет выигрывать, если ему известна выигрышная стратегия.
Рубеж XIX и XX веков ознаменован появлением трудов, принадлежащих наиболее плодовитым авторам в области занимательной математики: англичанину Генри Эрнесту Дьюдени (1857—1930) и американцу Сэму Лойду (1841—1911). Множество задач и головоломок, которые до сих пор приковывают внимание игроков, описаны в книгах именно этих двух великих авторов.
Генри Эрнест Дьюдени, помимо прочего, является автором «Кентерберийских головоломок» (1907) и «Математических головоломок и развлечений» (1917). Последняя содержит одну из лучших и обширнейших коллекций математических игр всех времен.
Среди огромной коллекции головоломок Дьюдени выделяются криптарифмы — ребусы с числами, в которых цифры обозначаются буквами так, что одинаковым буквам соответствуют одинаковые цифры, а разным буквам — разные цифры. Один из известных примеров: РЕШИ + ЕСЛИ = СИЛЕН, причем наибольшая цифра в числе СИЛЕН не превышает 5. Нужно заменить буквы цифрами так, чтобы получилось верное равенство. (Ответ к этому криптарифму следующий: 9382 + + 3152 = 12534.)
Сэм Лойд опубликовал большинство своих задач в газетах и журналах. В одну книгу под названием «Энциклопедия головоломок» их собрал его сын Сэм Лойд-младший в 1914 году, уже после смерти отца. Среди головоломок Лойда — знаменитая задача о соединении 9 точек, расположенных в форме квадрата 3 × 3, четырьмя прямыми линиями, не отрывая карандаша от бумаги (либо то же для 16 точек, квадрата 4 × 4 и шести линий), а также множество задач о расположении чисел определенным образом. Например, нужно расположить числа от 1 до 8 в вершинах куба так, чтобы сумма чисел на каждых четырех вершинах одной грани была одинаковой.
Традиции Дьюдени и Лойда продолжились и в XX веке. Среди ведущих авторов первой половины XX века выделяется Морис Крайчик (1882—1957), составитель нескольких книг о математических играх и редактор бельгийского журнала «Сфинкс». После Второй мировой войны на этой арене господствовал Мартин Гарднер (1914—2010), автор множества книг и статей, публиковавшихся на протяжении более 25 лет в научно-популярном журнале Scientific American (русская версия носит название «В мире науки»). Почти до самой смерти Гарднер продолжал публиковать новые издания своих работ. Всего из-под его пера вышло свыше 70 книг, среди которых Origami, Eleusis and The Soma Cube («Оригами, элузис и кубики сома»), вышедшая в 2008 году. Помимо собственных работ, он познакомил читателей с многими интересными играми, среди которых «Жизнь» Джона Конвея и «Элузис» Роберта Эббота (1956).
В каждой игре существует некая цель и определенные правила, и в этом элузис не похож ни на одну из них, ведь цель этой игры — угадать правила, придуманные одним из игроков, причем каждая партия играется по новым правилам. Игра рассчитана на 4-8 игроков, и для нее достаточно трех колод карт и нескольких фишек. Партия состоит из числа раундов по числу игроков. В каждом раунде один из игроков раздает остальным по 14 карт, после чего превращается в «бога игры», создателя правил, и выкладывает последнюю карту на стол. Раздающий должен записать на листе бумаги секретное правило, по которому формируется последовательность карт. Правила могут быть очень простыми (красное — черное или чет — нечет), но их можно придумать бесчисленное множество: четные после красных и нечетные после черных, четыре четных разной масти и четыре нечетных одной масти. В интересах того, кто придумывает правила, — сделать их неочевидными, но и не слишком сложными, так как если никто не поймет правил, игра получится неинтересной. Остальные игроки пытаются понять правило, не говоря при этом ни слова. Они по очереди выкладывают по одной карте, пытаясь сформировать ряд из «правильных» карт. «Бог игры» сообщает, является карта «правильной» (в этом случае она кладется в конец ряда) или «неправильной» — в этом случае она кладется под последнюю правильную карту, а игрок, сделавший неверный ход, получает в качестве штрафа две новые карты из колоды. Начиная с 40-й карты, ошибочный ход наказывается выходом из игры.
Игра заканчивается, когда одному из игроков удалось избавиться от всех своих карт или когда все игроки покинули игру.
В книге «Десять игр, которые ни на что не похожи» Роберта Эббота подробно описана эта великолепная игра.
Среди других авторов XX века — Яков Перельман, один из основоположников русской школы занимательной науки, француз Пьер Берлокен и англичане Иэн Стюарт, Брайан Болт и Дэвид Уэллс. Каждый из них является автором множества книг и статей в различных периодических изданиях. Заслуживают внимания и испанские авторы, которые в своих книгах о математических играх и головоломках также попытались сделать математику ближе к широкой публике.Наиболее известные среди них — Мариано Матаиш, Мигель де Гусман и Фернандо Корбалан. Их труды вкупе с книгами уже упомянутых авторов — неистощимый источник задач, игр и математических развлечений.
Появление теории игр
Важная часть этой книги, а именно главы 4 и 5, посвящена теории игр. В ней показывается, что рано или поздно все математические понятия и модели находят применение в реальном мире, даже если изначально они никак не были связаны. Это справедливо и для анализа игр.
Хороший игрок тот, кто во время игры совершает наиболее верные ходы. Цель анализа игр заключается именно в том, чтобы найти верные ходы и, если такое возможно, определить, какие ходы нужно совершать, чтобы всегда выигрывать. Это теоретически возможно в конечных играх, где не фигурируют случайные события. Однако игра может быть столь масштабной, что это помешает определить выигрышную стратегию.
Теория игр появилась в работах Джона фон Неймана, в частности в книге «Теория игр и экономическое поведение», опубликованной им совместно с экономистом Оскаром Моргенштерном в 1944 году. Изначально в теории игр шла речь об абстрактных играх для двух и более игроков, где определены выигрыш и проигрыш для каждого игрока в зависимости от совершенного хода. Как правило, игроки ходят одновременно и не знают стратегию соперников. Эти игры, используемые как математические модели, изначально применялись при анализе экономических ситуаций. Фон Нейман и Моргенштерн показали способ определения оптимальной стратегии для каждого игрока в играх этого типа. Фон Нейман предложил для решения этих задач так называемый принцип минимакса, а также расширил его для игр, в которых присутствуют случайные события (так называемые смешанные стратегии). Его методы оказались столь успешными, что математики и экономисты начали применять их при решении более сложных задач.
Прикладные методы из мира экономики, работающие на довольно простых моделях, непрерывно развивались на протяжении второй половины XX века. С появлением игр, в которых выигрыш одного игрока не обязательно означает проигрыш других, возникла идея о сотрудничестве, точнее сказать, о компромиссе между соперничеством и сотрудничеством. Так теоретические модели все больше приближались к реальности и постепенно начали находить применение не только в экономических науках, но и в военной сфере, политике, эволюционной биологии и даже в философии. Все эти научные дисциплины, столь далекие друг от друга, схожи в одном: они предполагают принятие решений в ситуациях, которые можно рассматривать как игры. Но в этом случае само слово «игра» обозначает уже не что-то развлекательное, но нечто рискованное. По мере того как формулировки этих игр приближались к реальности и, как следствие, усложнялись, они стали допускать решения, в которых учитываются не только математические параметры, но и моральные, этические и философские принципы поведения человека.
Одним из самых интересных аспектов теории игр, помимо ее порой удивительных результатов, является возможность вмешиваться в сферу действия общественных наук, которые по своей природе имеют дело со случайными событиями и где переменные описывают поведение отдельных личностей и групп людей. Так, развитие теории игр привело к появлению множества дилемм, которые касаются выбора между конфликтом, риском и сотрудничеством. В силу применимости к большому числу ситуаций подобные дилеммы составляют значительную часть теории игр. Среди наиболее известных отметим игру «Ястребы и голуби» и дилемму заключенного, о которых рассказывается в последней главе этой книги. Эти дилеммы некоторым образом показывают, насколько сложно изучать поведение человека. Они демонстрируют, что порой возможно не только изучить действия человека, но и определить их последствия, особенно когда они зависят от сочетания стратегий, используемых участниками.
Глава 2. Стратегические игры и решение задач
...Занимательная математика — это не только... разумное средство заполнения досуга взрослых людей. Занимательная математика — это прежде всего математика, причем в лучших своих образцах математика прекрасная. Недаром видный английский математик Дж. Литлвуд заметил, что хорошая математическая шутка лучше дюжины посредственных работ.
Игры можно классифицировать различными способами в зависимости от выбранного критерия: место для игры, число участников, длительность партии, уровень сложности и так далее. Применительно к математике игры можно разделить на две большие группы в зависимости от того, присутствуют в них случайные события или нет. Случайные события могут фигурировать как в начальных условиях игры, так и при совершении ходов. Например, в большинстве карточных игр карты раздаются игрокам случайным образом. Так же происходит и в домино. Напротив, начальное положение шахматных фигур строго определено и неизменно, как и в нардах, реверси или испанской игре парчис. Если говорить о случайности ходов, то во многих играх игроки свободно выбирают следующий ход из всех возможных, в то время как в других играх ходы зависят от броска одной или нескольких игральных костей. В этом случае игрок выбирает лишь из нескольких ходов, возможных для выпавшего числа очков на игральных костях.
Стратегическими называются игры, в которых никогда не происходит случайных событий. Всё определяют только решения игроков. Благодаря отсутствию случайности, игры этого типа можно проанализировать и найти способ победить. В некоторых случаях можно полностью определить выигрышную стратегию, в других ввиду сложности игры это не удастся, но можно показать, что подобная стратегия существует для одного из игроков. Несмотря на очевидное разнообразие игр такого типа, к ним применимо ограниченное число математических понятий и приемов, которые относятся преимущественно к арифметике (системы счисления и признаки делимости) и геометрии (равновесные ситуации, главным образом, симметрия).
Понятие выигрышной стратегии
В математике слово «игра» может обозначать как собственно игру, в которой участвует более одного игрока, имеются определенные правила, а цель игры — одержать победу в партии, так и математические развлечения и головоломки. В дальнейшем мы будем говорить об играх, в которых участвуют минимум два игрока. Эти игры также можно разбить на группы разными способами, но с точки зрения математики существует признак, определяющий две большие группы: игры с полной информацией и игры, в которых присутствует элемент неопределенности. В этой главе игры первой группы мы будем называть
Как следует изучив игру, мы задаемся вопросом: какие ходы нужно совершать, чтобы одержать победу в определенной партии? В азартных играх (например, в классической игре «Змеи и лестницы») этот вопрос не имеет смысла, поскольку игроки лишь двигают фишки согласно выпавшим очкам на игральных костях и следуют инструкциям на игровых клетках. Иными словами, здесь нет места для принятия решений, поэтому нет «хороших» или «плохих» игроков. Результат игр подобного типа полностью зависит от случая, поэтому определить какую-либо выигрышную стратегию невозможно. В этом смысле можно сказать, что интересность игры с точки зрения математики равна нулю.
Другой крайний случай — игры с полной информацией, в которых в любой момент можно узнать все возможные ходы и их последствия (как минимум в теории) и нет места неопределенности. Из всех подобных игр нам больше всего знакомы шахматы, хотя подобных стратегических игр, как традиционных (го, манкала, шашки, крестики-нолики), так и современных (гекс, ним, реверси, абалон и другие), существует великое множество.
Когда мы говорили об анализе игр этого типа, мы упомянули понятие выигрышной стратегии, то есть множества условий, позволяющих одному из игроков (как правило, речь идет об играх только для двух игроков) определить, как следует действовать в каждый момент времени, учитывая ходы, сделанные противником, чтобы одержать победу вне зависимости от ходов соперника. Существование выигрышной стратегии предполагает, что игра оканчивается победой одного из игроков, но в некоторых играх возможна и ничья, например, как в шахматах. В этом случае нужно вести речь о стратегиях, которые позволяют никогда не проигрывать. Когда стратегическая игра не может завершиться ничьей, можно убедиться, что существует выигрышная стратегия для первого или второго игрока, но это не означает, что подобную стратегию можно будет точно определить: игра может быть весьма сложной.
Возможно, наиболее обширный труд о стратегических играх носит название «Выигрышные стратегии ваших математических игр» в четырех томах (издан в 1982 году). Его авторами являются трое выдающихся математиков XX века: Элвин Берлекэмп (род. в 1940 году), профессор компьютерных наук в Калифорнийском университете в Беркли с 1971 года; Джон Конвей (род. в 1937 году), автор важных работ по теории конечных групп, профессор Кембриджского и Принстонского университетов, создатель игры «Жизнь», моделирующей жизнь клеток; Ричард Гай (род. в 1916 году), почетный профессор университета Калгари. Книга посвящена играм со следующими свойствами:
1. Это игры для двух игроков, делающих ходы поочередно.
2. Это игры, в которых определено одно начальное положение и существует конечное число ходов.
3. Это игры с полной информацией: в любой момент игрокам известны все возможные ходы.
4. Ни в начале игры, ни в процессе выполнения ходов нет места неопределенности.
5. Ход партии не допускает повторения ходов. Тот игрок, который не может совершить ход, проигрывает.
Допустим, что некая игра для двух игроков имеет следующие свойства:
1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.
2. Игроки совершают ходы поочередно.
3. В игре полностью отсутствует элемент неопределенности.
4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.
При этих условиях можно показать, что обязательно существует выигрышная стратегия для одного из двух игроков: первого (игрок А) или второго (игрок Б). Допустим, что выигрышной стратегии для игрока А не существует, иными словами, для игрока Б всегда будет существовать ход, на который у игрока А не найдется достойного ответа, и он проиграет. Это означает, что победит игрок Б. Таким образом, для него существует выигрышная стратегия. Подобные рассуждения лишь доказывают, что в подобных играх всегда существует выигрышная стратегия, но это не означает, что ее будет легко обнаружить.
Для игр, в которых партия не обязательно содержит конечное число ходов, применимость этого утверждения зависит от принятия так называемой аксиомы выбора. Эта известная и противоречивая математическая аксиома утверждает, что для каждого семейства (конечного или бесконечного) непустых непересекающихся множеств существует новое множество, образованное путем выбора определенного элемента из каждого множества этого семейства. С помощью этой аксиомы Банах, Мазур и Улам в 1930 году определили бесконечную игру и доказали, что в ней не существует выигрышной стратегии ни для одного из игроков.
Использование преимуществ и определение стратегий. Игра Ним и ей подобные
Вернемся к классификации игр и сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми. В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
Взаимосвязь между математикой и играми может касаться различных аспектов игр, как уже говорилось в первой главе. Применительно к стратегическим играм математика особенно полезна для определения выигрышной стратегии. Стратегическая игра очень похожа на процесс решения математической задачи: речь идет не о том, чтобы выиграть одну партию, совершая более удачные ходы, но о том, чтобы найти способ, как выигрывать всегда. По этой причине при определении выигрышных стратегий используются эвристические методы: способ «от обратного»; предположение, что игра «решена»; применение симметрии; проведение аналогии с другой, уже решенной игрой и прочие. Они аналогичны тем, что используются при решении математических задач. Поэтому когда для некоторой игры известна выигрышная стратегия, игра из развлечения превращается в решенную задачу. Понятно, что это верно только для определенных игр, которые выходят за рамки простых развлечений и описываются в математических теориях. О подобных теориях, порой достаточно сложных, мы поговорим далее.
Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она рассматривается далее в этой книге в параграфе «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если читатель незнаком с этой игрой, перед прочтением следующих страниц ему будет интересно попробовать сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2011), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру можно обобщить и дальше, изменив число фишек, которые можно брать на каждом ходу.
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, ..., 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 - n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Допустим, что на столе m фишек и каждым ходом можно брать от 1 до n фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?
Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:
1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n+1. Для этого на каждом ходу, если первый игрок берет p фишек (0<p<n+1), второй должен брать n+1—p фишек. Это число всегда положительно, так как находится на интервале от 0 до n.
2. Остаток от деления равен r(0<r<n+1).В этом случае существует выигрышная стратегия для первого игрока. На первом ходу он должен взять r фишек, оставив на столе число фишек, кратное n+1. Теперь он может действовать подобно второму игроку из первого случая. Иными словами, если второй игрок берет p фишек (0<p<n+1), первый должен взять n+1—р.
Это общее решение применимо к бесконечному множеству игр. Читатель может применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно m - 1, а не m.
Все подобные игры, в которых используется только одна группа фишек, можно считать упрощенными вариантами игры Ним, о которой мы поговорим далее.
Сложная стратегия: игра Ним
Все игры, о которых мы говорили до этого, можно обобщить еще больше: будем считать, что фишки лежат не в одной кучке, а в нескольких. Число кучек произвольное и конечное. В начале игры Ним фишки на столе лежат в нескольких кучках. Число фишек в кучках может отличаться. По правилам на каждому ходу игрок может брать минимум одну и максимум все фишки из выбранной кучки. Выигрывает тот, кто берет последнюю фишку. Также можно поменять правила и считать проигравшим того, кто должен взять последнюю фишку.
В начале игры на столе три кучки, состоящие из 1, 3 и 5 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?
Анализ игры позволяет увидеть, что такая стратегия существует для первого игрока, но из всех возможных начальных ходов только один гарантирует победу. Если читатель попрактикуется в этой игре, то увидит, что ни одному из игроков не выгодно делать следующие ходы:
1. Оставлять на столе две кучки с одинаковым числом фишек.
2. Забирать все фишки из одной кучки.
Если игрок А выполняет ход 1, игрок Б забирает все фишки из третьей кучки и выигрывает, симметрично повторяя ходы соперника. Если игрок А забирает из одной кучки гг фишек, игрок Б забирает столько же фишек из другой, и, когда А заберет все фишки из одной кучки, игрок Б заберет все фишки из другой и выиграет. Аналогично если игрок А совершит ход 2, то Б заберет нужное число фишек из той кучки, в которой их осталось больше. На столе останутся две одинаковые кучки, и игрок Б снова одержит победу, действуя как в предыдущем случае. Поэтому победу одерживает тот, кто заставит противника совершить один из двух «запрещенных» ходов. В рассматриваемом случае, если первый игрок берет 3 фишки из кучки, в которой 5 фишек, на столе останутся три кучки с 1, 2 и 3 фишками. Первый игрок выигрывает, так как его соперник будет вынужден или взять все фишки из одной кучки, или уравнять число фишек в двух кучках (оставив в них по 1 или по 2 фишки).
Очевидно, что это слишком частный случай и его сложно обобщить на произвольное число кучек и даже для трех кучек, но с большим числом фишек. Несмотря на это, математические методы позволяют найти выигрышную стратегию общего вида, применимую для любого количества кучек и фишек в каждой из них. Для этого нужно записать число фишек в каждой кучке в двоичной системе так, чтобы единицы были записаны под единицами. Каждым ходом четность как минимум в одном из столбцов будет меняться, так как после каждого хода будет изменяться только одно из чисел в одном или нескольких столбцах. Как минимум одна из цифр изменится с 1 на 0 или наоборот. Если в начальном расположении фишек сумма всех цифр каждого столбца четна, существует выигрышная стратегия для второго игрока: он должен ходить так, чтобы после хода сумма цифр во всех столбцах была четной. Первый игрок не может сделать такой ход. Если же хотя бы в одном столбце сумма цифр нечетна, то выигрышная стратегия существует для первого игрока: первым ходом он сможет сделать сумму цифр во всех столбцах четной и довести игру до победы.
Чтобы лучше понять суть этой стратегии, рассмотрим несколько примеров. Сначала мы рассмотрим три кучки с 1, 3 и 5 фишками (это игра 4, которую мы решили ранее). Затем мы перейдем к более привычной версии игры Ним под названием Мариенбад. В ней четыре кучки с 1, 3, 5 и 7 фишками.
В первом случае число фишек в кучках равно 1, 3 и 5.
1 в двоичной системе: 1
3 в двоичной системе: 11
5 в двоичной системе: 101
Сложим единицы в каждом столбце и увидим, что сумма цифр каждого столбца нечетная (справа налево: 3, 1 и 1). В этом случае существует выигрышная стратегия для первого игрока. Для этого ему нужно ходить так, чтобы суммы цифр во всех столбцах оставались четными. Единственный способ сделать это — забрать фишки из кучки, где их 5 (101), оставив 2 (10), то есть забрать 3 фишки из кучки с 5 фишками. Получим:
Поделиться книгой: