Задание 26 из ЕГЭ по информатике: задача 23
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. В начальный момент времени в куче находилось 1 ≤ S ≤ 37 камней.
За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 38 камней. При этом если в куче было не более 66 камней, то побеждает тот игрок, который сделал последний ход, в противном случае побеждает его соперник.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
Задание 1. а) Найдите все значения S, при которых Коля может выиграть первым ходом. Укажите все такие значения и соответствующие ходы Коли.
б) Определите, кто из игроков имеет выигрышную стратегию при S = 36, S = 35, S = 34. Опишите выигрышные стратегии для этих случаев.
Задание 2. Определите, кто из игроков имеет выигрышную стратегию при S = 18, S = 17. Опишите соответствующие выигрышные стратегии.
Задание 3. Определите, кто из игроков имеет выигрышную стратегию при S = 16. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах количество камней в позиции.
Объект авторского права ООО «Легион»
Вместе с этой задачей также решают:
Предприятие производит детали A и B, на их производство выделена конкретная сумма денег. Вам предоставлен полный перечень, какие детали можно изготовить. Каждую деталь из перечня м…
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным…
Два участника играют в игру «Три кучки». В их распоряжении есть три кучки камней. Каждым ходом игрок может взять от 1-го до 3-х камней, но только из одной из трёх кучек. Проигрывае…
