Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается, когда суммарное количество камней становится не менее 63. Побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 5 камней, во второй — $S$ камней, где $1 \leq S \leq 57$. Требуется определить значения $S$ и описать выигрышные стратегии игроков в трёх случаях: победа Пети за один ход; победа Пети своим вторым ходом независимо от хода Вани; победа Вани первым или вторым ходом при любой игре Пети, если Ваня не может гарантированно выиграть первым ходом.
Решение по шагам
9 шаговПетя может выиграть первым ходом, если после одного из разрешённых действий сумма камней станет не менее 63. Из позиции $(5,S)$ удвоение второй кучи даёт сумму $5+2S$, поэтому требуется $5+2S \geq 63$, то есть $S \geq 29$. При $S \geq 29$ это условие выполняется. Другие действия не дают меньшего значения $S$.
$$5+2S\geq 63\Longleftrightarrow S\geq 29$$Следовательно, в задании 1а подходят все значения $S$ от 29 до 57 включительно.
Для задания 1б рассмотрим первый ход Пети, после которого Ваня должен иметь возможность выиграть сразу. При $S=15$ Петя может неудачно удвоить вторую кучу и получить позицию $(5,30)$. Ваня удваивает вторую кучу и получает $(5,60)$, после чего сумма становится равной 65 и Ваня выигрывает первым ходом.
При меньших значениях $S$ ни один невыигрышный первый ход Пети не создаёт для Вани возможности немедленной победы. Поэтому минимальное значение в задании 1б равно $15$.
Для задания 2 берём $S=26$. Петя не может выиграть первым ходом, поскольку после удвоения второй кучи сумма равна $57$, а после удвоения первой — $36$.
Петя первым ходом удваивает первую кучу: $(5,26)\to(10,26)$. Из позиции $(10,26)$ любой ход Вани позволяет Пете закончить игру следующим ходом: после $(11,26)$ или $(20,26)$ Петя удваивает вторую кучу; после $(10,27)$ Петя также удваивает вторую кучу; после $(10,52)$ Петя добавляет один камень в первую кучу. Во всех случаях сумма становится не менее 63.
Для задания 3 подходит $S=15$. У Вани нет гарантированной победы первым ходом, так как после хода Пети $(5,15)\to(10,15)$ Ваня не может сразу получить сумму 63 или более. Однако после любого первого хода Пети Ваня может выбрать ход, переводящий игру в позицию, из которой он выигрывает следующим ходом независимо от ответа Пети.
Основные ветви стратегии Вани при $S=15$: если Петя получает $(6,15)$, Ваня удваивает первую кучу и получает $(12,15)$; если Петя получает $(10,15)$, Ваня удваивает первую кучу и получает $(20,15)$; если Петя получает $(5,16)$, Ваня удваивает первую кучу и получает $(10,16)$; если Петя получает $(5,30)$, Ваня удваивает вторую кучу и выигрывает сразу.
После позиций $(12,15)$, $(20,15)$ и $(10,16)$ Ваня выбирает удвоение той кучи, которая после хода Пети позволяет получить сумму не менее 63. Если Петя увеличивает большую кучу, Ваня удваивает другую; если Петя увеличивает меньшую кучу, Ваня удваивает большую. Все партии, соответствующие этой стратегии, заканчиваются победой Вани не позднее его второго хода.
1а) $S=29,30,\ldots,57$. 1б) Минимальное значение $S=15$. 2) $S=26$; Петя первым ходом удваивает первую кучу: $(5,26)\to(10,26)$, после чего отвечает на любой ход Вани так, чтобы получить сумму не менее 63. 3) $S=15$; Ваня использует стратегию перевода в позиции $(12,15)$, $(20,15)$ или $(10,16)$, из которых выигрывает не позднее второго хода.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только удвоение второй кучи и забывают про увеличение первой кучи на один камень.
Считают выигрышным ход, после которого сумма становится меньше 63.
В задании 2 описывают только один ответ Вани, хотя необходимо обеспечить победу Пети после любого хода Вани.
В дерево игры включают партии, в которых Ваня отклоняется от своей выигрышной стратегии.
Путают номер хода игрока с номером общего хода: второй ход Пети — это третий ход партии.