Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 98 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 33 камня и Паша утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход?
Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 34; 33; 32?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 11; 10?
Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 9? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
1. а) Паша может выиграть, если S = 35 или S = 12; 13; …; 32. При S = 35 первым ходом нужно добавить в кучу 1 камень, при остальных указанных значениях S нужно утроить количество камней.
б) При S = 32 Паша выигрывает в один ход, утраивая количество камней (см. п. а). При S = 33 или 34 утраивать количество камней не имеет смысла, так как после такого хода выигрывает противник. Поэтому можно считать, что единственный возможный ход – это добавление в кучу одного камня.
При S = 34 после такого хода Паши в куче станет 35 камней. В этой позиции ходящий (т. е. Валя) выигрывает (см. п. а)). Т. е. при S = 34 Паша (игрок, который должен ходить первым) проигрывает. Выигрышная стратегия есть у Вали.
При S = 33 после того, как Паша своим первым ходом добавит один камень, в куче станет 34 камня. В этой позиции ходящий (т. е. Валя) проигрывает (см. выше). Т. е. при S = 33 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши. Комментарии для экспертов. Скорее всего, решение экзаменуемого будет не столь подробным. Это не является ошибкой. Ученик может, например, нарисовать деревья всех возможных партий для указанных значений S. Другая возможность — (1) указать на то, что при S = 33 и 34 утраивать кучу смысла не имеет, и (2) последовательно сводить случай S = 34 к случаю S = 35, а случай S = 33 — к случаю S = 34.
2. При S = 11 после первого хода Паши в куче будет либо 12 камней, либо 33 камня. В обоих случаях выигрышная стратегия есть у игрока, который должен ходить, теперь это Валя. Случай S = 12 рассмотрен в задании 1(а), а случай S = 33 — в задании 1(б). Поэтому выигрышная стратегия есть у Вали.
При S = 10 выигрышная стратегия есть у Паши. Ему нужно первым ходом добавить 1 камень и получить кучу из 11 камней. Как показано выше, в этой ситуации выигрышная стратегия есть у игрока, который НЕ должен ходить, т. е. у Паши.
3. При S = 9 выигрышная стратегия есть у Вали. После первого хода Паши в куче может стать либо 10 камней, либо 27 камней. В обеих этих позициях выигрывает игрок, который будет делать ход (теперь это Валя).
Случай S = 10 рассмотрен в п. 2, случай S = 27 рассмотрен в п. 1(а).
В таблице изображено дерево возможных партий при описанной стратегии Вали. Заключительные позиции (в них выигрывает Валя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).