Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза.
Например, пусть в одной куче 15 камней, а в другой— 20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (16, 20), (15, 21), (45, 20), (15, 60). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в кучах становится не менее 120. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, когда в кучах всего будет 120 камней или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50, 3), (35, 15), (40, 10) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно утроить количество камней в первой куче.
Выполните следующие задания.
Задание 1. Для каждой из начальных позиций (5, 38), (20, 33) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (5, 37), (4, 38), (20, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (4, 37) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Задание 1. Если начальными являются позиции (5, 38), (20, 33), то выигрывает Саша своим первым ходом.
Если начальная позиция (5, 38), то после первого хода Коли может получиться одна из четырёх позиций: (6, 38) — всего 44, (15, 38) — всего 53, (5, 39) — всего 64, (5, 114) — всего 119. В каждом из полученных случаев суммарное число камней не превышает 120. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (6, 114), (15, 114), (5, 117), (5, 342). В каждом случае суммарное число камней не менее 120. Следовательно, Саша выигрывает своим первым ходом.
Если начальная позиция (20, 33), то после первого хода Коли может получиться одна из четырёх позиций: (21, 33) — всего 54, (60, 33) — всего 93, (20, 34) — всего 54, (20, 99) — всего 119. В каждом из полученных случаев суммарное число камней не превышает 120. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (21, 99), (60, 99), (20, 102), (20, 297). В каждом случае суммарное число камней не менее 120. Следовательно, Саша выигрывает своим первым ходом.
Задание 2. Если начальными являются позиции (5, 37), (4, 38), (20, 32), то выигрывает Коля своим вторым ходом.
Если начальной является одна из позиций (5, 37) или (4, 38), то, чтобы выиграть, Коля должен после своего хода получить позицию (5, 38). Для этого он должен увеличить на 1 число камней либо во второй куче (для позиции (5, 37)), либо в первой (для позиции (4, 38)). Считая позицию (5, 38) начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.
Если начальная позиция (20, 32), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 1. Тогда после его хода получится позиция (20, 33). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1.
Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым.
Значит, выиграет Коля своим вторым ходом.
Задание 3. Если начальной является позиция (4, 37), то выигрывает Саша не более чем за два хода.
После первого хода Коли из начальной позиции (4, 37) можно получить одну из следующих: (5, 37), (4, 38), (12, 37), (4, 111). Если на начало хода Саши будет одна из позиций (5, 37), (4, 38), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (12, 37), то Саша, утроив число камней во второй куче, получит позицию (12, 111) (здесь суммарное число камней 123 > 120) и выиграет.
Если на начало хода Саши будет позиция (4, 111), то Саша, утроив число камней во второй куче, получит позицию (4, 333) (здесь суммарное число камней 337 > 120) и также выиграет. Таблица выигрышных стратегий для позиции (4, 37). Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Коли (разобраны все ходы) |
1-й ход Саши (только ход по стратегии) |
2-й ход Коли (разобраны все ходы) |
2-й ход Саши (только ход по стратегии) |
|
| (4, 37) | (5, 37) | (5, 38) | (6, 38) | (6, 114) |
| (15, 38) | (15, 114) | |||
| (5, 39) | (5, 117) | |||
| (5, 114) | (5, 342) | |||
| (4, 38) | (5, 38) | (6, 38) | (6, 114) | |
| (15, 38) | (15, 114) | |||
| (5, 114) | (5, 342) | |||
| (5, 114) | (5, 342) | |||
| (12, 37) | (12, 111) | |||
| (4, 111) | (4, 333) | |||