Question

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 85 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 30 камней и Паша утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 35. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания. 1. а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши. б) У кого из игроков есть выигрышная стратегия при S = 28, 30, 32? Опишите выигрышные стратегии для этих случаев. 2. У кого из игроков есть выигрышная стратегия при S = 10, 8? Опишите соответствующие выигрышные стратегии. 3. У кого из игроков есть выигрышная стратегия при S = 6? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции

Answer 1

1. а) При каких значениях числа S Паша может выиграть в один ход? 
Ответ:
       * при 12<=S<=28 Паша увеличивает количество камней в 3 раза и выигрывает в 1 ход
       ** при S=34 и S=35 Паша увеличивает количество на 2 камня и выигрывает в 1 ход

б) У кого из игроков есть выигрышная стратегия при S = 28, 30, 32? 
Опишите выигрышные стратегии для этих случаев. 
       28: у Паши: П*3=84 - победа Паши
       30: у Паши: П+2=32 В+2=34 П+2=36 Победа Паши
       32: у Вали: П+2=34 В+2=36 Победа Вали

2. У кого из игроков есть выигрышная стратегия при S = 10, 8? 
Опишите соответствующие выигрышные стратегии. 
       10: у Вали: П*3=30 В+2=32 П+2=34 В+2=36 - Победа Вали
                          П+2=12 В*3=36 - победа Вали
        8: у Паши: П+2=10 В+2=12 П*3=36 -  Победа Паши
                                       В*3=30 П+2=32 В+2=34 П+2=36 -  Победа Паши
                                                                  В*3=96 -  Победа Паши   
    
3. У кого из игроков есть выигрышная стратегия при S = 6?
       6: у Вали

Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции
       см. фото