Решение: Стратегии в игре с числами
Два игрока, Петя и Ваня, играют в игру. На табличке записана пара неотрицательных целых чисел — позиция. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок должен заменить одно из чисел пары по своему выбору на сумму обоих чисел. Например, из позиции $(7, 2)$ можно получить $(7, 9)$ или $(9, 2)$.
Игра завершается, когда сумма чисел пары становится не менее 26. Побеждает игрок, сделавший последний ход, то есть первым получивший пару с суммой не менее 26.
Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. Опишите стратегию игрока, указав, какой ход он должен делать в любой ситуации, которая может встретиться при игре противника.
Задание 1. Перед ходом Пети на табличке записана пара чисел $(9, S)$. Укажите максимальное значение $S$, такое что Петя не может выиграть одним своим ходом.
Задание 2. Для начальной позиции $(5, 6)$ укажите, кто из игроков имеет выигрышную стратегию, и опишите эту стратегию.
Задание 3. Для начальной позиции $(2, 3)$ укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии. В узлах дерева указывайте позиции. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии.
Решение по шагам
8 шаговВ задании 1 из позиции $(9,S)$ Петя может получить $(9,9+S)$ с суммой $18+S$ или $(9+S,S)$ с суммой $9+2S$. Чтобы Петя не мог выиграть одним ходом, обе суммы должны быть меньше 26.
$$18+S<26,\quad 9+2S<26$$Получаем $S<8$ и $S<8{,}5$. Максимальное неотрицательное целое значение — $S=7$.
В задании 2 из позиции $(5,6)$ Петя может перейти в $(5,11)$ или $(11,6)$. В позиции $(5,11)$ Ваня заменяет число 5 на сумму чисел и получает $(16,11)$, сумма равна 27. В позиции $(11,6)$ Ваня заменяет число 6 на сумму чисел и получает $(11,17)$, сумма равна 28.
Следовательно, в задании 2 выигрышная стратегия есть у Вани: после любого первого хода Пети немедленно получить сумму не менее 26.
В задании 3 Петя из позиции $(2,3)$ может сделать ход в $(2,5)$ или $(5,3)$. Если Петя получает $(2,5)$, Ваня переходит в $(7,5)$. Если Петя получает $(5,3)$, Ваня переходит в $(5,8)$.
Из позиции $(7,5)$ Петя может получить $(7,12)$ или $(12,5)$. Ваня отвечает соответственно переходом в $(19,12)$ или $(12,17)$ и сразу получает сумму не менее 26.
Из позиции $(5,8)$ Петя может получить $(5,13)$ или $(13,8)$. Ваня отвечает соответственно переходом в $(18,13)$ или $(13,21)$ и сразу получает сумму не менее 26.
Таким образом, после любого первого хода Пети Ваня выбирает указанный ход, а затем при любом ответе Пети сразу завершает игру. Поэтому в задании 3 выигрышная стратегия также есть у Вани.
1) $S=7$. 2) Выигрывает Ваня: из $(5,11)$ он получает $(16,11)$, а из $(11,6)$ — $(11,17)$. 3) Выигрывает Ваня. Его стратегия и дерево партий: $(2,3)\to(2,5)\to(7,5)\to(7,12)\to(19,12)$ или $(2,3)\to(2,5)\to(7,5)\to(12,5)\to(12,17)$; $(2,3)\to(5,3)\to(5,8)\to(5,13)\to(18,13)$ или $(2,3)\to(5,3)\to(5,8)\to(13,8)\to(13,21)$. В каждой конечной позиции сумма не менее 26.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только один из двух возможных ходов в задании 1.
Путают игрока, делающего ход из позиции, с игроком, который получил эту позицию.
В дерево задания 3 включают ответы, которые выигрывающий игрок не обязан делать.
Забывают указать ход выигрывающего игрока после каждого возможного ответа соперника.