Решение: Каменная игра с двумя кучами
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч по своему выбору один камень или увеличить количество камней в куче в два раза. Например, из позиции $(10, 7)$ можно получить позиции $(11, 7)$, $(20, 7)$, $(10, 8)$ и $(10, 14)$. Игра завершается, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 5 камней, во второй — $S$ камней, где $1 \leq S \leq 69$. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. В описание стратегии не следует включать ходы, не являющиеся безусловно выигрышными.
Выполните задания 1–3:
1а) Укажите все значения $S$, при которых Петя может выиграть за один ход.
1б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$, при котором это возможно.
2) Укажите значение $S$, при котором Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Опишите стратегию Пети.
3) Укажите значение $S$, при котором Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Решение по шагам
6 шагов1а. Из начальной позиции $(5,S)$ Петя может выиграть одним ходом, если удвоение второй кучи даёт сумму не менее 75: $5+2S\geq75$. Отсюда $S\geq35$. Удвоение первой кучи требует $10+S\geq75$, то есть $S\geq65$, что уже входит в найденный диапазон.
$$35\leq S\leq69$$1б. Петя может сделать невыигрышный ход, удвоив первую кучу: $(5,S)\to(10,S)$. Ваня затем удваивает вторую кучу. Для победы Вани нужно $10+2S\geq75$, поэтому $S\geq32{,}5$. Минимальное целое значение — $S=33$.
2. Возьмём $S=32$. Петя не может выиграть первым ходом, поскольку после удвоения второй кучи сумма равна 69. Петя удваивает первую кучу и получает позицию $(10,32)$. Ваня может получить одну из позиций $(11,32)$, $(20,32)$, $(10,33)$ или $(10,64)$. В первых трёх случаях Петя удваивает вторую кучу, а из $(10,64)$ добавляет один камень. Во всех случаях Петя выигрывает вторым ходом.
3. Возьмём $S=31$. Если Петя делает ход $(5,31)\to(6,31)$, Ваня удваивает первую кучу и получает $(12,31)$. Если Петя получает $(10,31)$ удвоением первой кучи, Ваня добавляет камень во вторую кучу и получает $(10,32)$. Если Петя увеличивает вторую кучу и получает $(5,32)$, Ваня удваивает первую кучу и получает $(10,32)$. Если Петя удваивает вторую кучу и получает $(5,62)$, Ваня удваивает вторую кучу и немедленно выигрывает.
Из позиций $(12,31)$ и $(10,32)$ любой ход Пети создаёт Ване возможность выиграть следующим ходом. Например, из $(12,31)$ после ходов Пети $(13,31)$, $(24,31)$, $(12,32)$ или $(12,62)$ Ваня соответственно удваивает вторую кучу, удваивает вторую кучу, удваивает вторую кучу или добавляет камень. Из $(10,32)$ после ходов Пети $(11,32)$, $(20,32)$, $(10,33)$ или $(10,64)$ Ваня соответственно удваивает вторую кучу, удваивает вторую кучу, удваивает вторую кучу или добавляет камень.
Таким образом, при $S=31$ Ваня выигрывает своим первым ходом после хода Пети $(5,62)$, а во всех остальных случаях — своим вторым ходом. Гарантированно выиграть первым ходом Ваня не может, поскольку после хода Пети $(5,31)\to(6,31)$ ни один ход Вани не даёт сумму не менее 75.
1а) $S=35,36,\ldots,69$. 1б) $S=33$. 2) $S=32$: Петя сначала удваивает первую кучу; затем после $(11,32)$, $(20,32)$ или $(10,33)$ удваивает вторую кучу, а после $(10,64)$ добавляет один камень. 3) $S=31$. Стратегия Вани: после $(6,31)$ перейти в $(12,31)$; после $(10,31)$ или $(5,32)$ перейти в $(10,32)$; после $(5,62)$ сразу удвоить вторую кучу. Из полученных позиций Ваня выигрывает следующим ходом при любом ходе Пети.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Указывать $S=65$ как единственный ответ в задании 1а и не учитывать удвоение второй кучи.
Считать выигрышным ходом позицию с суммой 74: игра заканчивается только при сумме не менее 75.
Включать в стратегию Пети или Вани ходы, которые не гарантируют победу при любом ответе соперника.
Строить полное дерево игры вместо дерева, соответствующего выбранной выигрышной стратегии Вани.