Решение: Стратегии в игре с парами чисел
Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно из чисел пары на сумму обоих чисел. Игра заканчивается, когда сумма чисел становится не менее 67. Побеждает игрок, сделавший последний ход.
Задание 1. Перед ходом Пети записана пара $(12,S)$. Найдите минимальное значение $S$, при котором Петя может выиграть одним ходом.
Задание 2. Для начальной позиции $(15,14)$ определите, кто имеет выигрышную стратегию, и опишите эту стратегию.
Задание 3. Для начальной позиции $(4,8)$ определите, кто имеет выигрышную стратегию. Постройте дерево всех партий, возможных при реализации этой стратегии. В узлах дерева указывайте позиции. Дерево не должно содержать партии, невозможные при реализации выигрышной стратегии.
Решение по шагам
7 шаговВ задании 1 Петя может заменить число 12 на сумму чисел. Тогда получится позиция $(12+S,S)$ с суммой $12+2S$. Требуется $12+2S\ge67$, поэтому $S\ge27{,}5$. Так как $S$ — целое число, минимальное значение равно 28.
$$12+2S\ge67\Rightarrow S\ge27{,}5$$В задании 2 из позиции $(15,14)$ Петя может получить либо $(29,14)$, либо $(15,29)$. В первом случае Ваня заменяет 14 на сумму и получает $(29,43)$, сумма которой равна 72. Во втором случае Ваня заменяет 15 на сумму и получает $(44,29)$, сумма которой равна 73. В обоих случаях Ваня немедленно выигрывает.
$$29+43=72\ge67,\qquad 44+29=73\ge67$$Следовательно, в задании 2 выигрышная стратегия есть у Вани: после первого хода Пети заменить меньшее число получившейся пары на сумму обоих чисел.
В задании 3 Петя из позиции $(4,8)$ может перейти в $(12,8)$ или $(4,12)$. В обоих случаях Ваня имеет выигрышную стратегию. Если получена позиция $(8,12)$, Ваня переходит в $(12,20)$. Если получена позиция $(4,12)$, Ваня переходит в $(4,16)$.
$$(4,8)\to(8,12)\to(12,20)\quad\text{или}\quad(4,8)\to(4,12)\to(4,16)$$Из позиции $(12,20)$ любой ход Пети приводит к одной из позиций $(20,32)$ или $(12,32)$, после чего Ваня получает конечную позицию: соответственно $(32,52)$ или $(32,44)$.
Из позиции $(4,16)$ Петя может перейти в $(16,20)$ или $(4,20)$. Ваня отвечает соответственно переходом в $(20,36)$ или $(20,24)$. После этого любой ход Пети позволяет Ване получить сумму не менее 67.
Таким образом, в задании 3 выигрышная стратегия есть у Вани. Дерево партий при этой стратегии можно записать таблицей переходов: $(4,8)\to(8,12)$, затем $(8,12)\to(12,20)$; либо $(4,8)\to(4,12)$, затем $(4,12)\to(4,16)$. Далее Ваня каждый раз выбирает указанные ответы, приводящие к конечной позиции.
1) Минимальное значение $S$ равно 28. 2) Выигрышная стратегия есть у Вани: после любого первого хода Пети заменить меньшее число на сумму обоих чисел. 3) Выигрышная стратегия есть у Вани. Он отвечает переходом $(8,12)\to(12,20)$ или $(4,12)\to(4,16)$, а затем выбирает ход, приводящий к позиции с суммой не менее 67.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только один из двух возможных ходов, не рассматривая замену каждого числа пары.
Считают выигрышной позицию, в которой сумма уже не менее 67, хотя такая позиция является конечной.
В задании 3 строят полное дерево игры, включая ходы, которые выигрышный игрок не стал бы делать.
Не указывают ответную стратегию для всех ходов соперника.