Задание 26 из ЕГЭ по информатике: задача 26
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой - 10 камней; такую позицию в игре будем обозначать (20; 10). Тогда за один ход можно получить любую из четырёх позиций: (21; 10); (60; 10); (20; 11); (20; 30).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 167. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 167 или больше камней. В начальный момент в первой куче было 40 камней, во второй куче - S камней; 1 ≤ S ≤ 126.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть за один ход, и соответствующие выигрышные ходы. Если при некотором значении S Коля может выиграть несколькими способами, достаточно указать один выигрышный ход.
б) Укажите, сколько существует значений S, при которых Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.
Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:
- Коля не может выиграть за один ход;
- Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.
Для указанного значения S опишите выигрышную стратегию Коли.
Задание 3. Укажите значение S, при котором одновременно выполняются два условия:
- у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;
- у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Саши. Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.
В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.
Объект авторского права ООО «Легион»
Вместе с этой задачей также решают:
В магазине решили провести акцию «каждый третий товар бесплатно». Дядя Миша решил хорошенько сэкономить и разделил товары на группы по три товара, собираясь заплатить за каждую гру…
По результатам прошедшей олимпиады Google Code Jam участников награждают дипломами I, II и III степени. Если несколько участников набрали одинаковое количество баллов, они получают…
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным…
