Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 68. Побеждает игрок, сделавший последний ход. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника.
Задание 1. Для каждой из начальных позиций (4, 21), (7, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 2. Для каждой из начальных позиций (4, 20), (6, 20) укажите, кто имеет выигрышную стратегию, и опишите её. Задание 3. Для начальной позиции (5, 20) укажите, кто имеет выигрышную стратегию, опишите её и постройте дерево всех партий, возможных при реализации этой стратегии. В дерево не включайте партии, невозможные при реализации стратегии выигрывающего игрока.
Условие как в банке ФИПИ — открыть и сверить
| Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы,
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 68. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 68 или больше камней.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (5, 21), (4, 22), (8, 20) и (7, 21) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно утроить количество камней во второй куче. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от дальнейшей игры противника.
Задание 1. Для каждой из начальных позиций (4, 21), (7, 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 2. Для каждой из начальных позиций (4, 20), (6, 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 3. Для начальной позиции (5, 20) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
| ||
| |
Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.
Открыть разбор1Мягкая — с чего смотретьуровень 1 из 3
Рассматривайте позиции как выигрышные или проигрышные для игрока, которому предстоит ход. Проигрышная позиция должна переводиться любым ходом противника в выигрышную.
2Наводящая — какие числа считатьуровень 2 из 3
Для позиции (5, 20) рассмотрите четыре возможных первых хода Пети: (6, 20), (15, 20), (5, 21) и (5, 60).
3Прямая — фактически решениеуровень 3 из 3
При начальной позиции (5, 20) выигрышная стратегия есть у Вани: после хода Пети из (6, 20) нужно получить позицию (7, 20), а после остальных трёх ходов можно немедленно утроить одну из куч и завершить игру.