Задание 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. Кто выигрывает при п…

В магазине решили провести акцию «каждый третий товар бесплатно». Дядя Миша решил хорошенько сэкономить и разделил товары на группы по три товара, собираясь заплатить за каждую гру…

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в кучу один ил…