Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в два раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 59. Побеждает игрок, сделавший последний ход. Выигрышная стратегия должна гарантировать победу независимо от ходов противника.
Для каждой указанной начальной позиции определите игрока, имеющего выигрышную стратегию, и опишите эту стратегию. Для позиции (5, 25) постройте дерево всех партий, возможных при реализации выигрышной стратегии; невозможные при этой стратегии партии в дерево включать нельзя.
Решение по шагам
8 шаговДля анализа каждой позиции перечисляют все возможные ходы: увеличение одной из куч на 1 и удвоение одной из куч. Если после хода сумма становится не менее 59, игра заканчивается победой сделавшего ход.
Для позиции (4, 27) выигрышная стратегия принадлежит Ване. После любого первого хода Пети Ваня выбирает ход, переводящий игру в позицию, из которой Петя не может гарантированно выиграть, а затем отвечает симметричным или компенсирующим ходом, сохраняя выигрышную для себя конфигурацию.
Для позиции (6, 26) выигрышная стратегия принадлежит Пете. Петя первым ходом переводит игру в позицию, являющуюся проигрышной для Вани; после любого ответа Вани Петя повторно выбирает ход, ведущий к позиции с гарантированной победой.
Для позиции (4, 26) выигрышная стратегия принадлежит Ване. Его стратегия состоит в том, чтобы после первого хода Пети переводить игру в одну из заранее рассчитанных проигрышных позиций и не выбирать ходы, которые дают Петру возможность немедленно получить выигрышную позицию.
Для позиции (5, 26) выигрышная стратегия принадлежит Пете. Петя первым ходом выбирает переход в проигрышную для Вани позицию, после чего на каждый ход Вани отвечает ходом из своей выигрышной стратегии.
Для позиции (6, 25) выигрышная стратегия принадлежит Ване. После первого хода Пети Ваня выбирает единственный тип ответа, сохраняющий проигрышность позиции для следующего игрока.
Для позиции (5, 25) выигрышная стратегия принадлежит Пете. Петя первым ходом переводит игру в позицию, после которой любой ход Вани допускает ответ Пети, приводящий к завершению игры на следующем ходу или к позиции, из которой победа уже гарантирована.
Дерево партий для позиции (5, 25) строится рекурсивно: в корне записывается (5, 25), далее — только допустимые ходы Пети из его выигрышной стратегии, затем все возможные ходы Вани, а после каждого такого хода — только ответ Пети, предусмотренный стратегией. Ветвь заканчивается, когда сумма камней становится не менее 59.
1) (4, 27) — Ваня; (6, 26) — Петя. 2) (4, 26) — Ваня; (5, 26) — Петя; (6, 25) — Ваня. 3) (5, 25) — Петя; дерево строится только по ходам, предусмотренным выигрышной стратегией Пети.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Неверно считать выигрышной любую позицию, из которой можно сделать сильный ход: нужно учитывать все возможные ответы противника.
Включать в дерево полное дерево игры, включая ходы, которые игрок с выигрышной стратегией никогда не делает.
Забывать, что игра заканчивается сразу после получения суммы 59 или больше.
Путать удвоение количества камней в куче с добавлением такого же количества камней.