Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в 3 раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 29. Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Для решения этой задачи, давайте проанализируем возможные состояния игры и действия игроков. Петя начинает первый, а затем ходит Ваня. Задача заключается в том, чтобы найти минимальное значение \( S \) (количество начальных камней), при котором у Вани есть возможность выиграть после первого неудачного хода Пети. Вот, как стратегически подойти к этой задаче: ### Анализ возможных состояний 1. **Петя делает первый ход.** - Из количества камней \( S \) он может: - Увеличить количество камней на 1, получив \( S + 1 \) - Увеличить количество камней в 3 раза, получив \( 3S \) 2. **Состояние победы:** - Игра заканчивается, когда количество камней достигает 30 или больше. Таким образом, любое состояние, где у одного из игроков есть возможность сделать так, чтобы кучи камней стало 30 или больше — это выигрыш для того игрока, который делает этот ход. ### Выигрышная стратегия Вани Чтобы понять, при каком начальном количестве камней Пети не удастся выиграть, а Ване — да, давайте рассмотрим, как он может выиграть: - Если после первого хода Пети Ваня может сделать так, чтобы у Пети не осталось выигрышных шагов, он выигрывает. Так как Ваня выигрывает после неправильного первого хода Пети, давайте проверим возможные значения S от 1 до 29. 1. **Начнем от 29**: - \( S = 29 \): - Петя ходит (может сделать 30 или 87), Ваня выигрывает. 2. **Пробуем уменьшать S**: - \( S = 28 \): - Петя ходит (может сделать 29 или 84). Ваня не может выиграть здесь сразу. - \( S = 27 \): - Петя (может сделать 28 или 81). Ваня снова не может выиграть сразу. - Мы видим, что пока Петя может либо увеличить \( S \) на 1, либо утроить и снова Ваня не может выиграть сразу. ### Найдем «плохие» позиции для Пети Посмотрим на позиции, которые являются выигрышными (где игрок, находящийся на очереди, может гарантированно выиграть): - Если \( S \) от 30 и выше — это выигрывающее состояние. - Если \( S = 29 \) (Петя делает 30): - Если \( S = 28 \) (Петя делает 29): - Если \( S = 27 \), то если Петя делает 28, Ваня может сделать 29. ### Определим критические состояния Петя может потерять, если: - после его хода Ваня всегда находится в выигрывающей позиции. Таким образом, при \( S = 19 \): - Петя (имея 19) играет (20, 57). - Ваня после этого может перевести в 21 или выиграть, если увеличится. ### Вывод Получается, что минимальное значение \( S \), после которого Ваня может гарантированно победить из положения Пети, — это: \[ S = 19 \] Именно с этим количеством камней Ваня может выиграть свою партию, когда Петя сделает неправильный первый ход.