Решение: Игра с двумя кучами камней
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень либо увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 74. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах всего будет 74 камня или больше.
Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. Описание выигрышной стратегии должно содержать только безусловно выигрышные ходы.
Задание 1. Для каждой из начальных позиций (4, 23), (7, 22) укажите, кто имеет выигрышную стратегию, и опишите эту стратегию.
Задание 2. Для каждой из начальных позиций (4, 22), (6, 22) укажите, кто имеет выигрышную стратегию, и опишите эту стратегию.
Задание 3. Для начальной позиции (5, 22) укажите, кто имеет выигрышную стратегию, опишите её и постройте дерево всех партий, возможных при реализации этой стратегии. В дерево не включайте партии, невозможные при реализации выигрышной стратегии.
В ответе необходимо привести развернутое обоснование.
Решение по шагам
5 шаговДля каждой позиции рассматриваются четыре возможных хода: (a+1,b), (3a,b), (a,b+1), (a,3b). Если после хода сумма не менее 74, ход является немедленно выигрышным.
В позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. После любого хода Пети Ваня получает возможность закончить игру или перевести её в позицию, из которой Петя вынужден открыть Ване немедленную победу.
$$W(4,23)=W(7,22)=\text{Ваня}$$В позиции (4,22) Петя утрачивает преимущество первого хода: любой его ход позволяет Ване применить выигрышный ответ. То же верно для позиции (6,22). Следовательно, в обеих позициях выигрышная стратегия есть у Вани.
$$W(4,22)=W(6,22)=\text{Ваня}$$В позиции (5,22) Петя имеет выигрышную стратегию: первым ходом он увеличивает первую кучу на один камень и получает позицию (6,22). Далее Петя использует выигрышные ответы, соответствующие позиции (6,22), не допуская перехода в позицию, где Ваня может завершить игру.
$$(5,22)\to(6,22)$$Дерево партий строится только по ходам, совместимым с этой стратегией Пети. В каждой вершине указываются все возможные ходы Вани, а для каждого такого хода — единственный безусловно выигрышный ответ Пети. Ветки, в которых Петя делает невыигрышный ход, в дерево не включаются.
Задание 1: в позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. Задание 2: в позициях (4,22) и (6,22) выигрышная стратегия есть у Вани. Задание 3: в позиции (5,22) выигрышная стратегия есть у Пети; первый ход — увеличить первую кучу на один камень: (5,22) → (6,22), после чего использовать выигрышные ответы по дереву партий.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать выигрышной любую позицию, из которой существует хотя бы один удачный ход, не проверяя все возможные ответы противника.
Включать в дерево партии, в которых игрок, обладающий стратегией, сам выбирает невыигрышный ход.
Забывать, что игра заканчивается сразу после достижения суммы 74 и более.
Путать позицию, выигрышную для игрока, которому предстоит ходить, с позицией, выигрышной для игрока, который ходил последним.