Ответ: Каменная игра с двумя кучами
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)$ сразу удвоить вторую кучу. Из полученных позиций Ваня выигрывает следующим ходом при любом ходе Пети.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч по своему выбору один камень или увеличить количество камней в куче в два раза. Например, из позиции $(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$, при котором Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Где здесь ошибаются
Указывать $S=65$ как единственный ответ в задании 1а и не учитывать удвоение второй кучи.
Считать выигрышным ходом позицию с суммой 74: игра заканчивается только при сумме не менее 75.
Включать в стратегию Пети или Вани ходы, которые не гарантируют победу при любом ответе соперника.
Строить полное дерево игры вместо дерева, соответствующего выбранной выигрышной стратегии Вани.