Подготовка к ЕГЭ и олимпиадам по информатике 2019 / Тренировочные варианты ЕГЭ

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант № EGE_INF_1802

Добавлен 16 декабря 2017 в 0:45. Изменён 17 июня 2018 в 17:03.Скачать PDF
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Задание

Три игрока, Паша, Вова и Тимур, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша, второй ход — Вова и третий ход — Тимур соответственно. За один ход игрок может добавить в кучу семь камней или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 22 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 40 или больше камней. В начальный момент в куче было 1 ≤ S ≤ 39 камней.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противников. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противников.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. Укажите все такие значения числа S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будут ходить Вова и Тимур. Для каждого указанного значения S опишите выигрышную стратегию Паши.

2. Известно, что Паша и Вова создали коалицию и играют согласованно. Укажите все такие значения числа S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Тимур. Для каждого указанного значения S опишите выигрышную стратегию Паши.

3. Известно, что Паша и Тимур создали коалицию и играют согласованно. Укажите все такие значения числа S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для наибольшего из указанных значений S опишите выигрышную стратегию Паши. Постройте дерево всех партий, возможных при этой выигрышной стратегии Паши (в виде рисунка или таблицы).