Задание 26 из ЕГЭ по информатике: задача 16
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 15 камней, а в другой 20 камней; такую позицию будем обозначать (15; 20). Тогда за один ход можно получить любую из четырёх позиций (16; 20), (15; 21), (45; 20), (15; 60). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в кучах становится не менее 150. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, когда в кучах всего будет 150 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50; 3), (40; 30), (48; 10) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно утроить количество камней в первой куче.
Выполните следующие задания.
Задание 1. Для каждой из начальных позиций (40; 29), (20; 43) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (40; 28), (39; 29), (20; 42) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (39; 28) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Объект авторского права ООО «Легион»
Вместе с этой задачей также решают:
В магазине решили провести акцию «каждый третий товар бесплатно». Дядя Миша решил хорошенько сэкономить и разделил товары на группы по три товара, собираясь заплатить за каждую гру…
На столе лежат карточки с числами от 1 до 9. Двое играют в игру. За один ход берётся одна карточка. Выигрывает тот, у кого есть три карточки с общей суммой 15. Кто выигрывает при п…
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из …
