Решение: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Первый ход делает Петя. За один ход игрок может добавить в одну из куч 3 камня или увеличить количество камней в одной из куч в 2 раза. Игра завершается, когда суммарное количество камней в двух кучах становится не менее 135. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 13 камней, во второй куче — $S$ камней; $1 \leq S \leq 121$. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение $S$, при котором такая ситуация возможна.
Решение по шагам
5 шаговЧтобы Ваня выиграл первым ходом после неудачного хода Пети, ход Пети должен быть неокончательным, а из полученной позиции Ваня должен иметь ход, после которого сумма станет не менее 135.
При малых значениях $S$ выгоднее всего Петя удваивает вторую кучу: $(13,S) \rightarrow (13,2S)$. После этого Ваня также удваивает вторую кучу.
После двух последовательных удвоений второй кучи суммарное количество камней равно $13 + 4S$. Для победы Вани требуется $13 + 4S \geq 135$.
Получаем $4S \geq 122$, то есть $S \geq 30{,}5$. Минимальное целое значение — $S=31$.
При $S=31$ Петя получает позицию $(13,62)$, а Ваня удваивает вторую кучу и получает позицию $(13,124)$ с суммой $137$, поэтому Ваня выигрывает.
Где здесь ошибаются
Считать победной уже позицию после хода Пети.
Забыть, что Ваня может удвоить ту же кучу ещё раз.
Не проверить минимальность значения $S$.