Анализ с конца – метод поиска выигрышных позиций

Игры и стратегии

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

Прежде чем приступить к рассмотрению задач, нам потребуется осознать, что соображения типа «если он ходит так, то я хожу так» не являются, как правило, решением игры. На самом деле, для решения игровой задачи необходимо, во-первых, грамотно и четко сформулировать стратегию, во-вторых, доказать, что она действительно ведет к выигрышу, и, в-третьих, показать, что описанная стратегия реализуема. Особое внимание следует обратить именно на третий пункт: именно про него чаще всего забывают и именно из-за него, казалось бы, совершенно правильная стратегия оказывается не более чем бессмысленным набором действий, который далеко не всегда сможет обеспечить выигрыш в игре.

Но не будем спешить. Заметим лишь, что во всех задачах ответить надо на один и тот же вопрос – кто побеждает: начинающий (первый) или его соперник (второй)? Свой ответ, естественно, Вам потребуется аргументировать.

Игры-шутки

Первый класс игр, о которых пойдет речь – игры-шутки. Это игры, исход которых не зависит от того, как играют соперники. Поэтому для решения такой игры, по сути, не нужно указывать выигрышную стратегию: она будет состоять для игрока лишь в выборе, следует ли ему ходить первым либо же вторым. Достаточно лишь доказать, что выигрывает тот или иной игрок (независимо от того, как будет проходить игра).

Задача 1. Числа от 1 до 20 выписаны в строчку. Игроки по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитывается результат. Если он четен, то выигрывает первый игрок, если нечетен, то второй.

Решение. Заметьте, что четность результата не зависит от расстановки плюсов и минусов игроками, а зависит только от количества нечетных чисел в первоначальном наборе. Так как в данном случае их 10 (т. е. четное число), то в такой игре выигрывает первый игрок, причем независимо от того, как будет ходить он и его соперник.

Задача 2. Дана клетчатая доска размерами

а) 9 × 10; б) 10 × 12; в) 9 × 11.

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

Решение. Эта игра – не совсем шутка. В ней выигрывающий, допустив ошибку, может проиграть. Эта ошибка состоит в том, что он после своего хода оставляет невычеркнутые клетки только в одном столбце или только в одной строке, предоставляя противнику возможность выиграть в один ход. Проигравшим в этой игре является, тем самым, тот, кто сделает этот роковой ход. Заметим, что оставшуюся после вычеркивания горизонтали часть клетчатой доски m×n можно представить себе как доску (m – 1)×n. Аналогично, после вычеркивания вертикали остается доска m×(n – 1). Ситуация, в которой каждый ход является «роковым», только одна – это доска 2×2. Таким образом, выигрывает игрок, после хода которого она возникла. Однако, как мы видели, при каждом ходе суммарное количество горизонталей и вертикалей на доске уменьшается на 1. Поэтому четность этой суммы в начале игры определяет победителя. В пункте а) выигрывает первый игрок, а в пунктах б) и в) – второй. Заметим, что в пункте б) решающим соображением может быть и симметричная стратегия второго игрока, с принципами которой мы ознакомимся чуть позже.

Задача 3. Двое по очереди ломают шоколадку 6×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Кто выиграет в этой игре?

Решение. Основное соображение: после каждого хода количество кусков увеличивается ровно на 1. Сначала был один кусок. В конце игры, когда нельзя сделать ни одного хода, шоколадка разломана на маленькие дольки 1×1. А их 48! Таким образом, игра будет продолжаться ровно 47 ходов. Последний, 47-й ход (так же, как и все другие ходы с нечетными номерами) сделает первый игрок. Поэтому он в этой игре побеждает, причем независимо от того, как будет играть.

Симметричные стратегии

Рассмотрим следующую игру.

Задача 4. Двое по очереди кладут пятаки на круглый стол, причем так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать ход.

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

Определение 1. Выигрышной стратегией игрока будем называть такую последовательность его действий, при которой он может обеспечить себе выигрыш в игре независимо от ходов соперника.

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

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

Задача 5. Двое по очереди ставят слонов в клетки шахматной доски так, чтобы слоны не били друг друга (цвет слонов значения не имеет). Проигрывает тот, кто не может сделать ход.

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

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

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

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

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

Схема решения игровой задачи:

1. Поиск какой-либо выигрышной стратегии для одного из игроков, затем, в случае ее видимого отсутствия, поиск стратегии для другого игрока.

2. Формулировка найденной стратегии с подробным описанием действий игрока, который должен выиграть. Доказательство её выигрышности (либо обоснование, почему один из игроков выигрывает при любом раскладе).

3. Доказательство реализуемости описанной стратегии.

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

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

Таким образом, при решении игровых задач мы всегда считаем, что наш противник приложит все усилия для своего выигрыша и, соответственно, нашего проигрыша. Одним словом – противник никогда не бывает глуп!

Симметричные стратегии

(продолжение)

Вспомним, о чем идет речь, когда мы говорим о симметричных стратегиях.

Задача 1. Двое по очереди ставят крестики и нолики в клетки доски 9 × 9. Начинающий ставит крестики, его соперник – нолики. В конце подсчитывается, сколько имеется строчек и столбцов, в которых крестиков больше, чем ноликов – это очки, набранные первым игроком. Количество строчек и столбцов, где ноликов больше – очки второго. Тот из игроков, кто наберет больше очков, побеждает.

Решение. Выигрывает первый. Первым ходом он ставит крестик в центральную клетку. Затем после каждого хода второго игрока первый ставит крестик в центрально-симметричную клетку.

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

Утверждение. При симметричной стратегии после каждого хода одного из игроков позиция становится симметричной. Поэтому если возможен очередной ход другого игрока, то возможет и симметричный ему ответный ход первого.

Вспомним, что на прошлой лекции мы встречались с понятием симметричной стратегии, причем во всех задачах она имела ярко выраженный геометрический смысл. Оказывается, что симметричная стратегия вовсе не обязана иметь чисто геометрический смысл. Своего рода симметричность вполне может прослеживаться, к примеру, в количестве каких-либо предметов.

Задача 2. Имеется две кучки камней – по 7 в каждой. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать.

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

Симметрия в этой задаче состоит в равенстве числа камней в кучках. Далее мы рассмотрим еще несколько игр на ту же идею, где симметрия имеет скорее не геометрический, а «логический» смысл.

Задача 3. Есть две кучки камней: в одной – 30, в другой – 20. За ход разрешается брать любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать.

Решение. Выигрывает первый. Первым ходом он уравнивает количество камней в кучках, взяв 10 камней из второй кучки. Затем играет, как в задаче 2.

Замечание. Обратите внимание, что нередко симметричная стратегия имеет применение не только в тех задачах, где начальные условия в некотором смысле симметричны (будь то, к примеру, симметричное игровое поле или одинаковое количество предметов в двух кучках), а и в таких играх, где на некотором ходе к этой симметричности можно прийти.

К примеру, в задаче 3 первый игрок первым своим ходом сделал игровую ситуацию симметричной, тем самым обеспечив себе выигрышную симметричную стратегию в дальнейшем.

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

Решение. Выигрывает первый игрок. Первым своим ходом он может провести хорду, по обе стороны от которой расположено одинаковое количество вершин – по 9. После этого, на каждый ход второго он отвечает аналогичным «симметричным» ходом по другую сторону от этой хорды.

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

Выигрышные позиции

Рассмотрим игру.

Задача 5. Ладья стоит на поле a1. За ход разрешается сдвинуть ее на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8.

Решение. В этой игре побеждает второй игрок. Его стратегия очень проста: каждым своим ходом он возвращает ладью на большую диагональ a1–h8. Объясним, почему, играя так, второй игрок выигрывает. Дело в том, что первый игрок каждый раз вынужден будет уводить ладью с этой диагонали, а второй игрок после этого будет иметь возможность вернуть ладью на линию a1–h8. Так как поле h8 принадлежит диагонали, то на него сумеет встать именно второй игрок.

Проанализируем это решение.

Нам удалось выделить класс выигрышных позиций (ладья стоит на одной из клеток диагонали a1–h8), обладающих следующими свойствами:

1) завершающая позиция игры – выигрышная;

2) за ход из одной выигрышной позиции нельзя попасть в другую;

3) из любой невыигрышной (проигрышной) позиции за один ход можно попасть в какую-то выигрышную.

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

А теперь рассмотрим еще пару задач на выигрышные позиции.

Задача 6. Король стоит на поле a1. За один ход его можно передвинуть на одно поле вправо, или на одно поле вверх, или на одно поле по диагонали «вправо-вверх». Выигрывает тот, кто поставит короля на поле h8.

Решение. Выигрывает первый игрок. Занумеруем горизонтали и вертикали шахматной доски в естественном порядке. Координаты поля a1 – (1, 1), поля h8 – (8, 8). Выигрышными являются позиции, в которых король стоит на поле с четными координатами. Первый ход – на поле b2.

Задача 7. Игра начинается с числа 60. За ход разрешается уменьшить имеющееся число на любой из его делителей. Проигрывает тот, кто получит ноль.

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

Упражнение. Докажите, что предложенная в решении задачи 7 стратегия реализуема.

Сегодня мы подведем итог нашей последней темы этого семестра. Для этого давайте сначала вспомним, что такое выигрышные позиции.

Задача 1. На концах клетчатой полоски 1 × 20 стоит по шашке. За ход разрешается сдвинуть любую шашку в направлении другой на одну или на две клетки. Перепрыгивать шашкой через шашку нельзя. Проигрывает тот, кто не может сделать ход.

Решение. Выигрывает второй игрок. Выигрышными являются позиции, в которых между шашками находится кратное 3 число пустых клеток.

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

Анализ с конца – метод поиска выигрышных позиций

На прошлой лекции у Вас могло появиться ощущение, что поиск выигрышных позиций основан лишь на интуиции, а потому, как правило, сравнительно непрост. Возникает вполне естественный вопрос: существует ли некий общий метод поиска выигрышных позиций? Именно сейчас мы и познакомимся с общим методом, позволяющим найти выигрышные позиции во многих играх.

Опишем этот метод на примере уже разобранной задачи. Для этого вернемся к задаче про короля из предыдущей подтемы (задача 6 предыдущей лекции).

Попробуем найти выигрышные позиции, не вникая непосредственно в суть игры двух игроков, а опираясь исключительно на их свойства. Заметим в первую очередь, что, как и всегда, завершающая позиция игры (король стоит на h8) – выигрышная. Поэтому в клетку h8 нашей квадратной доски поставим «+» (см. рис. 1). Таким же образом мы будем отмечать все найденные выигрышные позиции в дальнейшем. В клетках, соответствующих проигрышным позициям, будем ставить «–».

+	– +             – –	+ – +             – –               +
Рис. 1	Рис. 2	Рис. 3

Поскольку позиции, из которых король может за один ход попасть на выигрышное поле h8 – проигрышные, то возникает расстановка, изображенная на рис. 2. С полей h6 и f8 за один ход можно попасть только на проигрышные поля. В этих клетках необходимо поставить «+» – они выигрышные (см. рис. 3). Только что полученные выигрышные позиции порождают набор новых проигрышных позиций – h5, g5, g6, f7, e7, e8 (см. рис. 4). Продолжим такое заполнение аналогичным образом (рисунки 5, 6). После получения очередного набора минусов мы отмечаем плюсом те поля, из которых каждый ход, разрешенный условием, ведет в проигрышную позицию. После этого отмечаем минусом те поля, из которых существует хотя бы один ход в выигрышную позицию. В итоге плюсы и минусы будут расставлены так, как показано на рисунке 7.

– + – +         – – – –             – +             – –	+ – + – +         – – – –           + – +             – –               +	– + – + – +     – – – – – –         – + – +         – – – –             – +             – –
Рис. 4	Рис. 5	Рис. 6
– + – + – + – + – – – – – – – – – + – + – + – + – – – – – – – – – + – + – + – + – – – – – – – – – + – + – + – + – – – – – – – –	– – – – – – – +               –               –               –               –               –               –               –	– – – – – – – + – – – – – – + –             – –             – –             – –             – –             – –             – –
Рис. 7	Рис. 8	Рис. 9

Только что описанный метод нахождения выигрышных позиций и называется анализом с конца.

Применяя его, к примеру, к задаче про ладью из предыдущей лекции (задача 5), легко получаем набор выигрышных позиций (практически не шевеля мозгами!). Действуя так, как показано на рисунках 8, 9, получаем расстановку знаков на рис. 10. Сравните ее с нашим решением на предыдущей лекции!

– – – – – – – + – – – – – – + – – – – – – + – – – – – – + – – – – – – + – – – – – – + – – – – – – + – – – – – – + – – – – – – –	– – – – – – – + – – – – – + – – – – – – – – + – – – + – – – – – + – – – – – – – – – – – + – – – – – – – – – – – – – – + – – – –
Рис. 10	Рис. 11

Далее рассмотрим следующую задачу.

Задача 2. Ферзь стоит на поле c1. За ход его можно передвинуть на любое число полей вправо, вверх или по диагонали «вправо-вверх». Выигрывает тот, кто поставит ферзя на поле h8.

Решение. Пользуясь анализом с конца, можно получить расстановку плюсов и минусов, показанную на рис. 11. Итак, выигрывает первый игрок, причем у него есть три варианта первого хода: на поля c5, e3, d1.

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

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

Задача 3. Имеется две кучки орешков: в первой – 7 орешков, во второй – 5. За ход разрешается брать любое количество орешков из одной кучки или поровну орешков из обеих кучек. Проигрывает тот, кто не может сделать ход.

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

Решение задачи 3. Покажем, как переформулировать эту задачу на уже привычном для нас языке метода выигрышных позиций с помощью геометрической интерпретации – шахматной доски. Пронумеруем вертикали и горизонтали шахматной доски числами от 0 до 7: вертикали – сверху вниз, а горизонтали – справа налево. Каждой позиции исходной игры сопоставим клетку, находящуюся на пересечении горизонтали с номером, равным числу орешков в первой кучке, и вертикали с номером, равным числу орешков во второй кучке. Теперь заметим, что ходу в первоначальной игре соответствует ход ферзя вправо, вверх или по диагонали «вправо-вверх» на шахматной доске. Таким образом, мы отождествили нашу игру с игрой из задачи 2! Отметим, что точно так же можно отождествить игры в задачах 2 и 5 из предыдущей лекции.

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

Далее рассмотрим еще несколько игровых задач, в которых Вы сможете самостоятельно оценить эффективность изучаемого нами метода.

Задача 4. Имеется две кучки по 11 спичек. За ход можно взять две спички из одной кучки и одну из другой. Проигрывает тот, кто не может сделать ход.

Решение. Выигрывает первый. Расстановка плюсов и минусов после переформулировки в терминах геометрической интерпретации метода выигрышных позиций – клетчатой доски 12 × 12 – показана на рис. 12.

Задача 5. Игра начинается с числа 0. За ход разрешается прибавить к имеющемуся числу любое натуральное число от 1 до 9. Выигрывает тот, кто получит число 100.

Решение. Эта задача является примером того, что геометрическая интерпретация необязательна для проведения анализа с конца. Здесь плюсами и минусами удобно помечать числа. Плюсом оказываются помечены числа, делящиеся на 10. Таким образом, выигрывает второй игрок.

+ + + + + + + + + + + + – – – – – – – – – – + + – – – – – – – – – – – + + + + + + + + + + – – + – – – – – – – + + – – + – – – – – – – – + – – + + + + + + + – – + – – + – – – – + + – – + – – + – – – – – + – – + – – + + + + – – + – – + – – + – + + – – + – – + – – + – – + – – + – – + – – +

Рис. 12