Решение: Игра с двумя кучами камней
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, во второй куче — $S$ камней, где $1 \leq S \leq 69$.
Выполните задания 1–3: определите значения $S$, при которых Петя или Ваня имеют выигрышную стратегию, опишите соответствующие стратегии и для задания 3 постройте дерево всех партий, возможных при реализации выигрышной стратегии Вани.
Решение по шагам
8 шаговИз начальной позиции $(7,S)$ Петя может выиграть первым ходом, если удвоение второй кучи даёт сумму не менее 77: $7+2S\geq77$, то есть $S\geq35$. Удвоение первой кучи даёт условие $14+S\geq77$, то есть $S\geq63$, которое уже входит в найденный диапазон. Поэтому ответ к заданию 1а: $S=35,36,\ldots,69$.
Для задания 1б достаточно взять минимальное $S$, при котором после неудачного хода Пети Ваня выигрывает сразу. При $S=18$ Петя может удвоить вторую кучу и получить позицию $(7,36)$. Ваня удваивает вторую кучу и получает $(7,72)$, сумма равна 79. При меньших значениях $S$ такой возможности нет. Ответ: $S=18$.
Для задания 2 берём $S=31$. Петя не выигрывает первым ходом, поскольку после любого его хода сумма остаётся меньше 77. Петя удваивает первую кучу и получает позицию $(14,31)$.
После хода Пети из $(14,31)$ Ваня может получить одну из позиций $(15,31)$, $(28,31)$, $(14,32)$ или $(14,62)$. В каждой из них Петя выигрывает следующим ходом: соответственно удваивает вторую кучу, удваивает первую кучу, удваивает вторую кучу или удваивает любую подходящую кучу. Следовательно, при $S=31$ Петя выигрывает своим вторым ходом независимо от хода Вани.
Для задания 3 берём $S=30$. Петя не может выиграть первым ходом. После каждого возможного первого хода Пети Ваня выбирает ход, после которого любой ответ Пети позволяет Ване выиграть следующим ходом либо Ваня выигрывает сразу.
Если Петя получает $(8,30)$, Ваня удваивает первую кучу и получает $(16,30)$. Если Петя получает $(14,30)$, Ваня также удваивает первую кучу и получает $(28,30)$. Если Петя получает $(7,31)$, Ваня удваивает первую кучу и получает $(14,31)$. Если Петя получает $(7,60)$, Ваня сразу удваивает вторую кучу и выигрывает.
Из позиций $(16,30)$, $(28,30)$ и $(14,31)$ любой ход Пети создаёт для Вани возможность немедленно получить сумму не менее 77. При этом Ваня не может гарантированно выиграть первым ходом из исходной позиции, поскольку, например, после хода Пети $(8,30)$ сумма ещё меньше 77 и Ваня должен подготовить выигрыш на следующий ход.
Дерево партий при стратегии Вани можно представить таблицей. В каждой строке указана позиция после хода Пети, затем ход Вани и позиция после него: $(7,30)\to(8,30)\to(16,30)$; $(7,30)\to(14,30)\to(28,30)$; $(7,30)\to(7,31)\to(14,31)$; $(7,30)\to(7,60)\to(7,120)$. Из позиций $(16,30)$, $(28,30)$ и $(14,31)$ все возможные ходы Пети приводят к немедленной победе Вани.
1а) $S=35,36,\ldots,69$; 1б) $S=18$. 2) $S=31$: Петя первым ходом удваивает первую кучу, получая $(14,31)$, после чего выигрывает вторым ходом при любом ходе Вани. 3) $S=30$: Ваня после ходов Пети $(8,30)$, $(14,30)$ и $(7,31)$ удваивает первую кучу, а после $(7,60)$ сразу удваивает вторую. Это гарантирует победу Вани первым или вторым ходом.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Указывать только один возможный ход противника вместо всех ходов, предусмотренных выигрышной стратегией.
Считать выигрышным ход, после которого сумма равна 76.
Включать в дерево полное дерево игры, включая ходы, которые не соответствуют выбранной стратегии Вани.
Забывать, что игрок, первым получивший сумму не менее 77, сразу выигрывает и дальнейшие ходы из этой позиции не рассматриваются.