Задание 26 из ЕГЭ по информатике: задача 17
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза.
Например, пусть в одной куче 15 камней, а в другой - 20 камней; такую позицию будем обозначать (15; 20). Тогда за один ход можно получить любую из четырёх позиций (16; 20), (15; 21), (45; 20), (15; 60). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в кучах становится не менее 120. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, когда в кучах всего будет 120 камней или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50; 3), (35; 15), (40; 10) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно утроить количество камней в первой куче.
Выполните следующие задания.
Задание 1. Для каждой из начальных позиций (5; 38), (20; 33) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (5; 37), (4; 38), (20; 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (4; 37) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Объект авторского права ООО «Легион»
Вместе с этой задачей также решают:
На столе лежат карточки с числами от 1 до 9. Двое играют в игру. За один ход берётся одна карточка. Выигрывает тот, у кого есть три карточки с общей суммой 15. Кто выигрывает при п…
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из …
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным…
