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

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

Два игрока, Полина и Виктория, играют в следующую игру. Перед игроками лежит куча конфет. Игроки ходят по очереди, первый ход делает Полина, второй ход — Виктория. За один ход игрок может взять:

• 1 или 2 конфеты, если количество конфет в куче делится на 3;
• 2 или 3 конфеты, если количество конфет в куче при делении на 3 даёт остаток один;
• 1 или 3 конфеты, если количество конфет в куче при делении на 3 даёт остаток два.

Например, имея кучу из 4 конфет, за один ход можно взять 2 или 3 конфеты. Каждый ход можно делать при наличии достаточного количества конфет. Игра завершается в тот момент, когда становится невозможно сделать очередной ход, при этом соответствующий игрок проигрывает. В начальный момент в куче было S > 0 конфет.

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

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

1. Укажите игрока, имеющего выигрышную стратегию в случае S=10. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы).

2. Укажите все значения S, не превосходящие 15, при которых Виктория имеет выигрышную стратегию. Опишите эти стратегии.

3. Укажите игрока, имеющего выигрышную стратегию в случае S=1000, а также его первый ход.