Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 68. Побеждает игрок, сделавший последний ход. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника.
Задание 1. Для каждой из начальных позиций (4, 21), (7, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 2. Для каждой из начальных позиций (4, 20), (6, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 3. Для начальной позиции (5, 20) укажите, кто имеет выигрышную стратегию, опишите её и постройте дерево всех партий, возможных при реализации этой стратегии. В дерево не включайте партии, невозможные при реализации стратегии выигрывающего игрока.
Решение по шагам
5 шаговПозиция (4, 20) выигрышна для Пети: первым ходом он утраивает вторую кучу и получает сумму 4 + 60 = 64? Нет, при правильном подсчёте после утроения второй кучи получается позиция (4, 60), сумма 64; поэтому этот ход не является немедленной победой. Выигрышная стратегия определяется обратным анализом позиций.
При обратном анализе проигрышными для игрока, которому предстоит ход, являются позиции (4, 21), (7, 20), (5, 20). Поэтому в позициях (4, 21) и (7, 20) выигрышная стратегия принадлежит Ване.
В позиции (4, 20) Петя имеет выигрышную стратегию: он переводит игру в проигрышную для Вани позицию (5, 20). В позиции (6, 20) Петя также выигрывает, переводя игру ходом +1 в позицию (7, 20).
В позиции (5, 20) выигрышная стратегия принадлежит Ване. Если Петя увеличивает первую кучу на один камень, получается (6, 20), и Ваня добавляет один камень в первую кучу, получая (7, 20). Если Петя утраивает первую кучу, получается (15, 20), после чего Ваня утраивает вторую кучу и получает сумму не менее 68. Если Петя увеличивает вторую кучу на один камень, получается (5, 21), после чего Ваня утраивает вторую кучу. Если Петя утраивает вторую кучу, получается (5, 60), после чего Ваня утраивает первую кучу.
Дерево партий при стратегии Вани состоит из четырёх ветвей, соответствующих четырём возможным ходам Пети из позиции (5, 20).
1) В позициях (4, 21) и (7, 20) выигрышная стратегия есть у Вани. 2) В позициях (4, 20) и (6, 20) выигрышная стратегия есть у Пети. 3) В позиции (5, 20) выигрышная стратегия есть у Вани. Дерево: (5,20) → (6,20) → (7,20); (5,20) → (15,20) → (15,60); (5,20) → (5,21) → (5,63); (5,20) → (5,60) → (15,60).
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать победной позицию, в которой сумма камней равна 67: следующий игрок ещё может добавить один камень и выиграть.
Включать в дерево все возможные ходы обоих игроков, включая ходы, которые не соответствуют выбранной выигрышной стратегии.
Забывать, что утроение одной кучи может сразу завершить игру, если новая сумма не менее 68.