Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 15 камней, а в другой—20 камней; такую позицию будем обозначать (15, 20). Тогда за один ход можно получить любую из четырёх позиций (17, 20), (15, 22), (30, 20), (15, 40).У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах всего будет 100 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50, 3), (35, 30), (40, 25) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно удвоить количество камней в первой куче.
Выполните следующие задания.
Задание 1. Для каждой из начальных позиций (10, 44), (20, 39) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (10, 42), (8, 44), (20, 37) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (8, 42) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Задание 1. Если начальными являются позиции (10, 44), (20, 39), то выигрывает Саша своим первым ходом.
Если начальная позиция (10, 44), то после первого хода Коли может получиться одна из четырёх позиций: (12, 44) — всего 56, (20, 44) — всего 64, (10, 46) — всего 56, (10, 88) — всего 98.
В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (12, 88), (20, 88), (10, 92), (10, 176).
В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.
Если начальная позиция (20, 39), то после первого хода Коли может получиться одна из четырёх позиций: (22, 39) — всего 61, (40, 39) — всего 79, (20, 41) — всего 61, (20, 78) — всего 98.
В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (22, 78), (40, 78), (20, 82), (20, 156). В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.
Задание 2. Если начальными являются позиции (10, 42), (8, 44), (20, 37), то выигрывает Коля своим вторым ходом.
Если начальной является одна из позиций (10, 42) или (8, 44), то, чтобы выиграть, Коля должен после своего хода получить позицию (10, 44). Для этого он должен увеличить на 2 число камней либо во второй куче (для позиции (10, 42)), либо в первой (для позиции (8, 44)). Считая позицию (10, 44) начальной, мы приходим к рассмотрению ситуации задания 1.
Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом. Если начальная позиция (20, 37), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 2. Тогда после его хода получится позиция (20, 39). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым.
Значит, выиграет Коля своим вторым ходом.
Задание 3. Если начальной является позиция (8, 42), то выигрывает Саша не более чем за два хода. После первого хода Коли из начальной позиции (8, 42) можно получить одну из следующих: (10, 42), (16, 42), (8, 44), (8, 84).
Если на начало хода Саши будет одна из позиций (10, 42), (8, 44), то он выиграет своим вторым ходом. Эти позиции, как начальные, были рассмотрены в задании 2. Если на начало хода Саши будет позиция (16, 42), то Саша, удвоив число камней во второй куче, получит позицию (16, 84) (здесь суммарное число камней 100) и выиграет.
Если на начало хода Саши будет позиция (8, 84), то Саша, удвоив число камней во второй куче, получит позицию (8, 168) (здесь суммарное число камней 176 > 100) и также выиграет.
Таблица выигрышных стратегий для позиции (8, 42). Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Коли (разобраны все ходы) |
1-й ход Саши (только ход по стратегии) |
2-й ход Коли (разобраны все ходы) |
2-й ход Саши (только ход по стратегии) |
|
| (8, 42) | (10, 42) | (10, 44) | (12, 44) | (12, 88) |
| (20, 44) | (20, 88) | |||
| (10, 46) | (10, 92) | |||
| (10, 88) | (10, 176) | |||
| (8, 44) | (10, 44) | (12, 44) | (123, 29) | |
| (20, 44) | (360, 29) | |||
| (10, 46) | (120, 30) | |||
| (10, 88) | (120, 87) | |||
| (16, 42) | (16, 84) | |||
| (8, 84) | (8, 168) | |||