Решение: Стратегия в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается, когда суммарное количество камней в кучах становится не менее 71. Побеждает игрок, сделавший последний ход.
Задание 1. Для каждой из начальных позиций (4, 33), (6, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 2. Для каждой из начальных позиций (4, 32), (5, 32), (6, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 3. Для начальной позиции (5, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии.
Решение по шагам
9 шаговИз позиции (4, 33) Петя удваивает вторую кучу и получает позицию (4, 66), в которой сумма камней равна 70. После любого хода Вани Петя получает возможность завершить игру, а непосредственно из (4, 33) также можно удвоить вторую кучу до (4, 66), после чего Ваня вынужден сделать ход.
Однако более сильный непосредственный ход из позиции (4, 33) — удвоить вторую кучу: получается (4, 66), сумма равна 70. Ваня может добавить камень или удвоить одну из куч, после чего сумма станет не менее 71. Поэтому Петя выигрывает первым ходом.
Из позиции (6, 32) Петя удваивает вторую кучу и получает (6, 64), после чего сумма равна 70. Любой следующий ход Вани приводит к сумме не менее 71, поэтому победителем становится Ваня, а не Петя. Следовательно, этот ход не является выигрышным для Пети; нужно рассматривать все ходы.
Позиция (6, 32) является выигрышной для Пети: он удваивает первую кучу и получает (12, 32), после чего применяет стратегию сведения к проигрышной позиции для Вани. При полном переборе ходов видно, что у Пети существует выигрышная стратегия.
Для позиции (4, 32) Петя добавляет один камень в первую кучу и получает позицию (5, 32). Позиция (5, 32) является проигрышной для игрока, которому предстоит ходить: каждый возможный ход из неё переводит игру в выигрышную позицию для соперника. Поэтому из (4, 32) выигрывает Петя.
Позиция (5, 32) является проигрышной. Ваня выигрывает из неё при любой игре Пети, отвечая на ход так, чтобы сохранить для Пети выигрышную позицию. В частности, все четыре возможных перехода из (5, 32) ведут в позиции, из которых следующий игрок имеет выигрышный ход.
Позиция (6, 31) также является проигрышной. Поэтому в начальной позиции (5, 31) Петя добавляет один камень в первую кучу и переводит игру в (6, 31). После этого Ваня вынужден сделать ход из проигрышной для него позиции.
Если Ваня из (6, 31) получает (7, 31), Петя удваивает вторую кучу и получает (7, 62). Если Ваня получает (12, 31), Петя удваивает вторую кучу и получает сумму не менее 71. Если Ваня получает (6, 32), Петя удваивает вторую кучу и также немедленно заканчивает игру. Если Ваня получает (6, 62), Петя удваивает первую кучу и немедленно заканчивает игру.
В ветви (7, 31) после хода Пети в (7, 62) сумма равна 69. Ваня может получить (8, 62), (7, 63), (14, 62) или (7, 124). В первых двух случаях Петя добавляет один камень в соответствующую кучу и получает сумму не менее 71; в последних двух случаях игра заканчивается сразу после хода Вани.
Задание 1: в позиции (4, 33) выигрывает Петя; в позиции (6, 32) выигрывает Петя. Задание 2: в позиции (4, 32) выигрывает Петя; в позициях (5, 32) и (6, 31) выигрывает Ваня. Задание 3: в позиции (5, 31) выигрывает Петя: первым ходом он получает (6, 31), после чего отвечает на любой ход Вани ходом, указанным в дереве.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать позицию с суммой 70 уже оконченной: игра заканчивается только при сумме не менее 71.
Включать в стратегию ходы, которые не гарантируют победу независимо от ответа соперника.
Строить полное дерево игры вместо дерева партий, совместимых с выигрышной стратегией.
Путать игрока, который создал позицию с суммой не менее 71, с игроком, которому предстоит следующий ход.