Шешімі: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч по своему выбору один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию обозначают (10, 5). За один ход можно получить позиции (11, 5), (20, 5), (10, 6), (10, 10). Для ходов у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 65. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 7 камней, во второй куче — $S$ камней; $1 \leq S \leq 57$.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными.
Задание 1. Укажите все значения $S$, при которых Петя может выиграть за один ход. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$, когда такая ситуация возможна.
Задание 2. Укажите значение $S$, при котором у Пети есть выигрышная стратегия, Петя не может выиграть за один ход, а своим вторым ходом может выиграть независимо от хода Вани. Для указанного значения $S$ опишите выигрышную стратегию Пети.
Задание 3. Укажите значение $S$, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, позволяющей гарантированно выиграть первым ходом. Для указанного значения $S$ опишите выигрышную стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Шешім по шагам
5 қадамИз начальной позиции $(7,S)$ Петя может выиграть одним ходом, если после одного из возможных ходов сумма станет не менее 65.
$$7+S+1\geq65 \Rightarrow S\geq57;\quad 14+S\geq65 \Rightarrow S\geq51;\quad 7+2S\geq65 \Rightarrow S\geq29$$Объединяя условия, получаем все значения $S$ от 29 до 57 включительно.
$$S\in\{29,30,\ldots,57\}$$Для задания 1б рассматриваем значения $S<29$. При $S=15$ Петя может неудачно удвоить вторую кучу и получить позицию $(7,30)$. Ваня удваивает вторую кучу и получает $(7,60)$, после чего сумма становится не менее 65.
$$7+2\cdot15=37;\quad 7+2\cdot30=67$$Для задания 2 подходит $S=15$. Петя первым ходом удваивает вторую кучу и получает $(7,30)$. После любого хода Вани Петя может завершить игру следующим ходом: из $(8,30)$, $(14,30)$, $(7,31)$ или $(7,60)$ существует ход, после которого сумма не менее 65.
$$S=15$$Для задания 3 подходит $S=21$. После любого первого хода Пети Ваня выбирает ход, переводящий игру в позицию, из которой он выигрывает следующим ходом. Если Петя делает ход $(7,21)\to(7,42)$, Ваня выигрывает сразу. При ходах $(7,21)\to(8,21)$, $(14,21)$ или $(7,22)$ Ваня удваивает вторую кучу; после любого следующего хода Пети Ваня завершает игру.
Задание 1: а) $S=29,30,\ldots,57$; б) $S=15$. Задание 2: $S=15$, первый ход Пети — удвоить вторую кучу. Задание 3: $S=21$; Ваня после первого хода Пети выбирает ход, обеспечивающий немедленный выигрыш следующим ходом.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Забывают, что игра заканчивается сразу после получения суммы не менее 65.
Считают выигрышным ход, после которого сумма меньше 65, без анализа ответа соперника.
В дерево выигрышной стратегии включают все возможные ходы, хотя нужно включать только ходы, совместимые со стратегией выигрывающего игрока.
Путают удвоение количества камней в одной куче с удвоением общей суммы.