Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра заканчивается, когда в куче не меньше 42 камней.
При этом, если число камней в куче не превышает 74, то побеждает игрок, сделавший последний ход, иначе выигрывает его оппонент. В начальный момент в куче было S камней; 1 ≤ S ≤ 41.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Опишите его стратегию.
б) У кого есть выигрышная стратегия при S = 38, 39, 40?
Задание 2
Кто из игроков имеет выигрышную стратегию при S = 19, 20?
Задание 3
Кто из игроков имеет выигрышную стратегию при S = 18?
В каждом случае опишите выигрышную стратегию. В задании 3 постройте дерево игры или таблицу, где ребрами являются сделанные ходы, а узлами - позиции камней.
Задание 1.
а) При 21 ≤ S ≤ 37 и S = 41 Паша может выиграть в один ход. При S = 41 он должен добавить 1 камень, а при 21 ≤ S ≤ 37 — увеличить число камней в куче в два раза.
б) При S = 40 и S = 38 выигрышная стратегия есть у Вали и при S = 39 — у Паши. Построим деревья игры.
Задание 2.
При S = 20, 19 выигрышная стратегия есть у Паши. Построим деревья игры.
Задание 3.
При S = 18 выигрышная стратегия есть у Вали. Построим дерево партий.