OpenFIPI 2.0
7D19E6
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче оказалось не более 46 камней,
то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 25 камней и Паша удвоит количество камней в куче, то игра закончится
и победителем будет Валя. В начальный момент в куче было S камней,
1 ≤ S ≤ 27.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход?
Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 13, 12? Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 11? Постройте дерево всех партий, возможных при этой выигрышной стратегии
(в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах количество камней в позиции.