Задание № 7204
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию в игре будем обозначать (6, 9). Тогда за один ход можно получить любую из четырёх позиций: (12, 9), (7, 9), (6, 10), (6, 18). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 81 или больше камней.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (21, 30) и (41, 20) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Задание 1
Для каждой из начальных позиций (10, 35), (6, 37) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2
Для каждой из начальных позиций (10, 34), (5, 37), (6, 36) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3
Для начальной позиции (5, 36) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Содержание верного ответа
Задание 1.
В начальных позициях (10, 35), (6, 37) выигрышная стратегия есть у Вани. При начальной позиции (10, 35) после первого хода Пети может получиться одна из следующих четырёх позиций: (11, 35), (20, 35), (10, 70), (10, 36). Каждая из этих позиций содержит менее 81 камня. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 81 камня, удвоив количество камней во второй куче. Для позиции (6, 37) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 37), (12, 37), (6, 38), (6, 74). Каждая из этих позиций содержит менее 81 камня. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 81 камня, удвоив количество камней во второй куче.
Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.
Задание 2.
В начальных позициях (10, 34), (5, 37) и (6, 36) выигрышная стратегия есть у Пети. При начальной позиции (10, 34) он должен первым ходом получить позицию (10, 35), из начальных позиций (5, 37) и (6, 36) Петя после первого хода должен получить позицию (6, 37). Позиции (10, 35) и (6, 37) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.
Задание 3.
В начальной позиции (5, 36) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (6, 36), (10, 36), (5, 37) и (5, 72). В позициях (10, 36) и (5, 72) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (6, 36) и (5, 37) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или на втором ходу.
В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом.
На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).
Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.