Математические головоломки и развлечения

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

На доске 4x4 все гораздо сложнее. Начинающий игру выигрывает наверняка лишь в том случае, если он сразу же занимает одну из четырех пронумерованных клеток (рис. 35).

Рис. 35

Сделав первый ход на любую другую клетку, он непременно проиграет. Начав игру с клеток 2 или 3, первый игрок одержит победу на пятом ходу; начав с клеток 1 или 4 — на шестом.

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

Специалисты по теории игр считают гекс особенно интересной игрой по следующей причине. Для игры на стандартной доске не известно, какой тактики необходимо придерживаться, чтобы наверняка обеспечить победу. Однако доказательством от противного можно довольно изящно показать, что для первого игрока всегда существует выигрышная стратегия на доске любого размера! (Доказательство существования обычно позволяет утверждать, что некий объект существует, но не дает никаких указаний, как его найти или построить.) Мы приведем лишь очень краткий набросок доказательства (его можно провести значительно более строго) в том виде, в каком его дал в 1949 году Джон Нэш.

1. Либо первый, либо второй игрок должен выиграть, поэтому либо для первого, либо для второго должна существовать выигрышная стратегия.

2. Предположим, что для второго игрока существует выигрышная стратегия.

3. Тогда первый игрок может обороняться следующим образом.

Сделав произвольный первый ход, он действует затем в соответствии с выигрышной стратегией второго игрока, описанной выше.

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

4. Лишняя фишка не может затруднить выигрыш первого игрока, потому что лишняя фишка — это всегда преимущество, а не помеха. Таким образом, первый игрок может выиграть.

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

6. Следовательно, выигрышная стратегия может существовать лишь для первого игрока.

Известно много разновидностей игры в гекс, в одной из них каждый играющий пытается заставить противника построить цепь. В соответствии с остроумным доказательством Р. Виндера, аспиранта-математика из Принстона, первый игрок в этой игре всегда может победить, если число клеток на стороне доски четное.

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

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

Они изображены на рис. 36.

Рис. 36Три задачи из игры в гекс.

Вопрос для всех трех задач один и тот же: найти такой первый ход, который обеспечивает «белым» победу.

* * *

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

Предлагались и другие, неромбические формы доски для гекса.

Например, создатель теории информации. К. Шеннон предложил игровое поле в форме равностороннего треугольника. Выигрывает тот, кто первым построит цепь, соединяющую все три стороны треугольника. Угловые клетки считаются принадлежащими обеим сторонам угла. Нэш доказал, что побеждает первый игрок. Метод доказательства без труда переносится и на случай треугольного игрового поля. (Здесь также выигрывает тот, кто начинает.)

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