Ответ: Стратегии в игре с кучами
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).
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 68. Побеждает игрок, сделавший последний ход. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника.
Задание 1. Для каждой из начальных позиций (4, 21), (7, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 2. Для каждой из начальных позиций (4, 20), (6, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 3. Для начальной позиции (5, 20) укажите, кто имеет выигрышную стратегию, опишите её и постройте дерево всех партий, возможных при реализации этой стратегии. В дерево не включайте партии, невозможные при реализации стратегии выигрывающего игрока.
Где здесь ошибаются
Считать победной позицию, в которой сумма камней равна 67: следующий игрок ещё может добавить один камень и выиграть.
Включать в дерево все возможные ходы обоих игроков, включая ходы, которые не соответствуют выбранной выигрышной стратегии.
Забывать, что утроение одной кучи может сразу завершить игру, если новая сумма не менее 68.