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