OpenFIPI 2.0

19

5

AF2C6D

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 32. Если при этом в куче оказалось не более 54 камней,
то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 29 камней и Паша удвоит количество камней в куче, то игра закончится
и победителем будет Валя. В начальный момент в куче было S камней,
1 ≤ S ≤ 31.

 

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

 

Выполните следующие задания.

1. а) При каких значениях числа S Паша может выиграть в один ход?

Укажите все такие значения и соответствующие ходы Паши.

б) У кого из игроков есть выигрышная стратегия при S = 30, 29, 28?

Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 15, 14? Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 13? Постройте дерево всех партий, возможных при этой выигрышной стратегии
(в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах  количество камней в позиции.