Решение: Стратегия в игре с парами чисел
Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно из чисел пары на сумму обоих чисел. Игра заканчивается, когда сумма чисел становится не менее 62. Побеждает игрок, сделавший последний ход.
Перед ходом Пети на табличке записана пара чисел $(15, S)$. Найдите минимальное значение $S$, при котором Петя может выиграть одним ходом.
Для начальной позиции $(12, 14)$ определите, кто имеет выигрышную стратегию, и опишите эту стратегию.
Для начальной позиции $(6, 7)$ определите, кто имеет выигрышную стратегию. Постройте дерево всех партий, возможных при выбранной выигрышной стратегии. В узлах дерева указывайте позиции. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей стратегии.
Решение по шагам
8 шаговВ задании 1 при замене числа 15 на сумму чисел получится позиция $(15+S,S)$ с суммой $15+2S$. При замене числа $S$ получится позиция $(15,15+S)$ с суммой $30+S$.
$$15+2S\geq 62\quad\text{или}\quad 30+S\geq 62$$Минимальное значение определяется первым неравенством: $S\geq 23$. При $S=23$ Петя заменяет число 15 на сумму чисел и получает позицию $(38,23)$ с суммой 61 — это недостаточно. Поэтому нужно внимательно выбрать ход: заменить число $S$ на сумму чисел. Тогда при $S=32$ получается сумма 62. Однако для выигрыша одним ходом при минимальном S достаточно заменить число 15: условие $15+2S\geq62$ даёт $S\geq24$ при целых S.
$$15+2S\geq62\Rightarrow S\geq\frac{47}{2}\Rightarrow S\geq24$$Следовательно, в задании 1 минимальное значение равно $S=24$. Ход Пети: $(15,24)\to(39,24)$, сумма равна 63.
В задании 2 из позиции $(12,14)$ Петя заменяет число 14 на сумму чисел и получает позицию $(12,26)$.
Если Ваня заменит число 12, получится $(26,26)$, после чего Петя заменяет одно из чисел на сумму и получает сумму 78. Если Ваня заменит число 26, получится $(12,38)$, после чего Петя заменяет число 12 на сумму и получает сумму 88. Значит, выигрышная стратегия есть у Пети.
В задании 3 рассмотрим оба возможных первых хода Пети. Если Петя получает $(13,7)$, Ваня переводит позицию в $(13,20)$. После этого любой ход Пети позволяет Ване завершить игру: $(13,20)\to(33,20)\to(33,53)$ или $(13,20)\to(13,33)\to(46,33)$.
Если Петя получает $(6,13)$, Ваня переводит позицию в $(19,13)$. После любого хода Пети Ваня выигрывает: $(19,13)\to(32,13)\to(32,45)$ или $(19,13)\to(19,32)\to(51,32)$.
Таким образом, в задании 3 выигрышная стратегия есть у Вани. Дерево партий содержит только ходы Вани, соответствующие его стратегии, и все возможные ответы Пети.
1) Минимальное значение $S=24$. 2) Выигрышная стратегия есть у Пети: $(12,14)\to(12,26)$; далее после $(26,26)$ или $(12,38)$ Петя выигрывает следующим ходом. 3) Выигрышная стратегия есть у Вани: после $(13,7)$ он ходит в $(13,20)$, а после $(6,13)$ — в $(19,13)$. Дерево: $(6,7)\to(13,7)\to(13,20)\to(33,20)\to(33,53)$ или $(13,33)\to(46,33)$; $(6,7)\to(6,13)\to(19,13)\to(32,13)\to(32,45)$ или $(19,32)\to(51,32)$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Неверно считать изменение общей суммы после хода.
В задании 1 принять значение $S=23$, не проверив, что сумма после хода равна только 61.
В задании 2 рассматривать только один возможный ответ Вани.
В задании 3 строить полное дерево игры вместо дерева, соответствующего выигрышной стратегии Вани.
Не указывать все возможные ответы Пети в позициях, где он не контролирует выбор хода.