помогите решить даю 25 баллов
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней.
Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в одну из куч (по своему выбору) два камня или
б) увеличить количество камней в куче в два раза.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в
обеих кучах всего будет 75 камней или больше.
Задание 1. Для каждой из начальных позиций (10, 32), (11, 31) укажите, кто из игроков имеет
выигрышную стратегию.
Задание 2. Для каждой из начальных позиций (10, 31), (11,30), (12,30) укажите, кто из игроков имеет
выигрышную стратегию.
Задание 3. Для начальной позиции (10,29) укажите, кто из игроков имеет выигрышную стратегию. Постройте
дерево всех партий, возможных при указанной выигрышной стратегии.
Ответы
Ответ:
Задание 1
Петя может выиграть при .
.
Задание 2
Возможное значение : . В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию . После хода Вани может возникнуть одна из четырёх позиций: , , , . В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче.
Замечание для проверяющего. Ещё одно возможное значение для этого задания – число . В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию . При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, утроив количество камней в большей куче. Достаточно указать одно значение и описать для него выигрышную стратегию.
Задание 3
Возможное значение : . После первого хода Пети возможны позиции: , , , . В позициях и Ваня может выиграть первым ходом, утроив количество камней во второй куче. Из позиций и Ваня может получить позицию . Эта позиция разобрана в п. . Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).