Математические головоломки и развлечения
Шрифт:
Рис. 33 Игра в гекс на доске со стороной из 11 шестиугольников. Черные выиграли.
Число шестиугольников может быть разным, но обычно предпочитают играть на доске, вдоль стороны которой укладывается одиннадцать шестиугольников. Две противоположные стороны ромба называются «черными», две другие — «белыми». Шестиугольники, находящиеся в углах ромба, относятся к обеим сторонам. Один игрок играет черными фишками, второй — белыми. Играющие по очереди ставят
Цепь может как угодно изгибаться, поворачивать. Фишки ставят до тех пор, пока кто-нибудь из игроков не выстроит свою цепь.
На рис. 33, например, видно, как победили «черные».
Игра никогда не кончается вничью, потому что один из участников может запереть другого, только построив свою цепь. Хотя правила гекса очень просты, тем не менее он оказывается удивительно тонкой математической игрой.
Придумал гекс датчанин Пит Хейн. В молодости Хейн провел несколько лет в Институте теоретической физики, а затем, сделав несколько технических изобретений, стал работать в промышленности. Так продолжалось до 1940 года, до вторжения немцев в Данию. Во время оккупации Хейн дважды уходил в подполье — он был председателем антинацистского демократического союза, распущенного с приходом нацистов. Именно во время оккупации он начал писать свои знаменитые эпиграммы под псевдонимом Кумбель.
[Три выпуска этих эпиграмм (Хейн назвал их «груками») изданы на английском языке под истинной фамилией автора: Нет Р. Grouks. I, II, III. — Copenhagen: 1966–1970. Некоторые эпиграммы Хейна были напечатаны на страницах журнала «Наука и жизнь» на русском языке. Вот одна из них, которая могла бы послужить эпиграфом к этой книге:
В задачах тех Ищи удачи, Где получить Рискуешь сдачи.]Они печатались в датской газете «Политикен», для которой Хейн одно время писал очерки и стихи, подписываясь своим настоящим именем. В одной только Дании, где население немногим больше четырех миллионов, было продано около четверти миллиона экземпляров сборника его стихов.
Идея игры в гекс пришла Хейну в голову, когда он размышлял над знаменитой топологической проблемой четырех красок. Эта проблема до сих пор не решена. Формулируется она следующим образом. Требуется доказать или опровергнуть утверждение: «Всякую карту можно раскрасить четырьмя красками так, что никакие две области, имеющие один и тот же цвет, не будут иметь общей границы». Хейн рассказал о придуманной им игре во время лекции.
Это было в 1942 году. Вскоре правила игры были опубликованы в газете «Политикен» и гекс стал необычайно популярен в Дании под названием «Многоугольники». Появились в продаже блокноты для игры с заранее напечатанными изображениями досок. «Политикен» из месяца в месяц публиковала задачи и премировала лучшие решения. Игра получила свое нынешнее название гекс лишь в 1952 году, после того как была выпущена фирмой «Паркер».
В 1948 году Джон Нэш, в то время аспирант-математик Принстонского университета, а позже один из самых выдающихся специалистов по теории игр в США, изобрел ту же игру независимо от Хейна. Она быстро увлекла математиков в Принстоне и в Институте высших исследований. Игра обычно называлась «Нэш» или «Ванная». Последнее название в основном было обязано тому, что студенты часто играли на шестиугольных плитках в ванных комнатах.
Читателям, которым захочется поиграть в гекс, следует заранее заготовить листки с начерченными на них досками. Ходы можно отмечать крестиками и кружками. Если вам больше нравится передвигать фишки на «настоящей» доске, можно нарисовать большую доску на листе толстого картона или сложить ее из шестиугольных керамических плиток. Если плитки достаточно
Чтобы понять все тонкости игры в гекс, лучше воспользоваться игровым полем, состоящим из небольшого числа шестиугольников.
На доске 2x2 (четыре шестиугольника) всегда выигрывает тот, кто делает первый ход. На доске 3x3 легко выиграть, если первый ход сделать в центр доски (рис. 34).
Рис. 34
«Черные» могут пойти двумя разными способами, заняв любой из двух шестиугольников, расположенных по обе стороны от центра, и поэтому на третьем ходу обязательно выигрывают.
На доске 4x4 все гораздо сложнее. Начинающий игру выигрывает наверняка лишь в том случае, если он сразу же занимает одну из четырех пронумерованных клеток (рис. 35).
Рис. 35
Сделав первый ход на любую другую клетку, он непременно проиграет. Начав игру с клеток 2 или 3, первый игрок одержит победу на пятом ходу; начав с клеток 1 или 4 — на шестом.
Для доски 5x5 еще можно доказать, что если первый игрок сразу же занимает центральную клетку, то он может выиграть на седьмом ходу. Для досок большего размера анализ становится слишком сложным. Стандартная доска 11 х 11 таит в себе астрономическое число усложнений, и полный анализ игры в гекс на такой доске находится за пределами человеческих возможностей.
Специалисты по теории игр считают гекс особенно интересной игрой по следующей причине. Для игры на стандартной доске не известно, какой тактики необходимо придерживаться, чтобы наверняка обеспечить победу. Однако доказательством от противного можно довольно изящно показать, что для первого игрока всегда существует выигрышная стратегия на доске любого размера! (Доказательство существования обычно позволяет утверждать, что некий объект существует, но не дает никаких указаний, как его найти или построить.) Мы приведем лишь очень краткий набросок доказательства (его можно провести значительно более строго) в том виде, в каком его дал в 1949 году Джон Нэш.
1. Либо первый, либо второй игрок должен выиграть, поэтому либо для первого, либо для второго должна существовать выигрышная стратегия.
2. Предположим, что для второго игрока существует выигрышная стратегия.
3. Тогда первый игрок может обороняться следующим образом.
Сделав произвольный первый ход, он действует затем в соответствии с выигрышной стратегией второго игрока, описанной выше.
Короче говоря, он становится вторым игроком, но с одной лишней фишкой, стоящей где-то на доске. Если, следуя стратегии, он должен будет пойти на ту клетку, которую занял первым ходом, он делает еще один произвольный ход. Если впоследствии игрок должен будет пойти на клетку, которую занял вторым произвольным ходом, он делает третий произвольный ход и т. д. Выбирая так ходы, он играет наилучшим образом, имея на доске одну лишнюю фишку.
4. Лишняя фишка не может затруднить выигрыш первого игрока, потому что лишняя фишка — это всегда преимущество, а не помеха. Таким образом, первый игрок может выиграть.
5. Предположение о существовании выигрышной стратегии для второго игрока приводит к противоречию, и потому его нужно отбросить.
6. Следовательно, выигрышная стратегия может существовать лишь для первого игрока.
Известно много разновидностей игры в гекс, в одной из них каждый играющий пытается заставить противника построить цепь. В соответствии с остроумным доказательством Р. Виндера, аспиранта-математика из Принстона, первый игрок в этой игре всегда может победить, если число клеток на стороне доски четное.