Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: - добавить в одну из куч (по своему выбору) 1 камень; - увеличить количество камней в одной из куч (по своему выбору) в 3 раза. Например, пусть в одной куче 20 камней, а в другой 30 камней, такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (21, 30), (20, 31), (60, 30), (20, 90). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 155. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 155 камней или больше. В начальный момент в первой куче было 15 камней, во второй куче — S камней, 1 \(\le\) S \(\le\) 139. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.

Решение:

Игра заканчивается, когда суммарное количество камней становится не менее 155. Побеждает тот, кто сделал последний ход.

Ваня выиграл своим первым ходом. Это значит, что после хода Пети у Вани была возможность сделать выигрышный ход.

Ходы Пети:

• Добавить 1 камень в первую кучу: \( 15+1=16 \). Новая позиция: \( (16, S) \).
• Добавить 1 камень во вторую кучу: \( S+1 \). Новая позиция: \( (15, S+1) \).
• Увеличить первую кучу в 3 раза: \( 15 \times 3 = 45 \). Новая позиция: \( (45, S) \).
• Увеличить вторую кучу в 3 раза: \( S \times 3 \). Новая позиция: \( (15, 3S) \).

Ваня выиграл своим первым ходом. Это означает, что Петя сделал неудачный ход, а Ваня смог завершить игру. После хода Пети суммарное количество камней было меньше 155, и Ваня добавил камней до 155 или более.

Рассмотрим ситуации после хода Пети, которые позволяют Ване выиграть:

1. Петя сделал ход \( (16, S) \). Ваня выигрывает, если \( 16 + S \ge 155 \), то есть \( S \ge 139 \). Так как \( S \le 139 \), то \( S = 139 \). Ваня делает ход, добавляя 1 камень во вторую кучу: \( 16 + (139+1) = 156 \).
2. Петя сделал ход \( (15, S+1) \). Ваня выигрывает, если \( 15 + S + 1 \ge 155 \), то есть \( S \ge 139 \). Так как \( S \le 139 \), то \( S = 139 \). Ваня делает ход, добавляя 1 камень в первую кучу: \( (15+1) + 139+1 = 156 \).
3. Петя сделал ход \( (45, S) \). Ваня выигрывает, если \( 45 + S \ge 155 \), то есть \( S \ge 110 \). Минимальное значение \( S = 110 \). Ваня может выиграть, например, добавив 1 камень во вторую кучу: \( 45 + (110+1) = 156 \).
4. Петя сделал ход \( (15, 3S) \). Ваня выигрывает, если \( 15 + 3S \ge 155 \), то есть \( 3S \ge 140 \), \( S \ge 46.67 \). Так как \( S \) — целое число, минимальное \( S = 47 \). Ваня может выиграть, например, добавив 1 камень в первую кучу: \( (15+1) + 3 \times 47 = 16 + 141 = 157 \).

Условие задачи гласит, что Петя сделал неудачный ход, а Ваня выиграл своим первым ходом. Это означает, что после хода Пети ситуация НЕ была выигрышной для Вани (то есть суммарное количество камней было меньше 155), но Ваня смог сделать ход, и сумма камней стала >= 155.

Нам нужно найти минимальное значение \( S \) (начальное количество камней во второй куче), при котором возможна такая ситуация. Рассмотрим наихудший сценарий для Пети (когда он делает ход, который наиболее выгоден Ване для победы).

Если Петя сделал ход \( (15, 3S) \), то для победы Ване нужно, чтобы \( 15 + 3S \ge 155 \), то есть \( 3S ≥ 140 \), \( S ≥ 46.67 \). Минимальное целое \( S \) равно 47.

Если Петя сделал ход \( (45, S) \), то для победы Ване нужно, чтобы \( 45 + S \ge 155 \), то есть \( S ≥ 110 \). Минимальное \( S \) равно 110.

Рассмотрим ход Пети \( (16, S) \) и \( (15, S+1) \). В обоих случаях для победы Вани требуется \( S ≥ 139 \). Минимальное \( S \) равно 139.

Наименьшее из найденных минимальных значений \( S \) равно 47, что достигается при ходе Пети \( (15, 3S) \).

Чтобы Петя сделал неудачный ход, и Ваня выиграл, начальное \( S \) должно быть таким, чтобы Петя не мог сразу выиграть (сделать сумму >= 155). И Ваня своим ходом мог выиграть.

Если \( S = 47 \), то Петя может сделать ход \( (15, 3 \times 47) = (15, 141) \). Сумма = 156. Петя выиграл. Это противоречит условию.

Чтобы Ваня выиграл своим первым ходом, Петя ДОЛЖЕН сделать ход, после которого сумма камней < 155, но Ваня может сделать ход, и сумма станет >= 155.

Рассмотрим, когда Ваня может выиграть. Это происходит, если после хода Пети, сумма камней \( K < 155 \), но \( K + \text{ход Вани} ≥ 155 \).

Пусть Петя сделал ход \( (15, 3S) \). Тогда суммарное количество камней равно \( 15 + 3S \). Для того чтобы Петя не выиграл сразу, \( 15 + 3S < 155 \), то есть \( 3S < 140 \), \( S < 46.67 \). Максимальное целое \( S \) здесь равно 46.

Если \( S=46 \), Петя сделал ход \( (15, 3 \times 46) = (15, 138) \). Сумма = 153. Теперь ход Вани. Ваня может добавить 1 камень в первую кучу: \( 16 + 138 = 154 \) (не выиграл). Или добавить 1 камень во вторую кучу: \( 15 + 139 = 154 \) (не выиграл). Или увеличить первую кучу в 3 раза: \( 15 \times 3 + 138 = 45 + 138 = 183 \). Ваня выиграл.

Таким образом, если \( S = 46 \), то Петя может сделать ход \( (15, 138) \), и Ваня выиграет. Это подходит под условие.

Рассмотрим ход Пети \( (45, S) \). Сумма = \( 45 + S \). Чтобы Петя не выиграл, \( 45 + S < 155 \), то есть \( S < 110 \). Максимальное целое \( S \) равно 109.

Если \( S = 109 \), Петя сделал ход \( (45, 109) \). Сумма = 154. Теперь ход Вани. Ваня может добавить 1 камень во вторую кучу: \( 45 + 110 = 155 \). Ваня выиграл.

Сравнивая \( S=46 \) и \( S=109 \), минимальное значение \( S \) равно 46.

Проверим другие ходы Пети:

Если Петя сделал ход \( (16, S) \). Сумма = \( 16 + S \). Чтобы Петя не выиграл, \( 16 + S < 155 \), то есть \( S < 139 \). Максимальное целое \( S \) равно 138.

Если \( S = 138 \), Петя сделал ход \( (16, 138) \). Сумма = 154. Теперь ход Вани. Ваня может добавить 1 камень во вторую кучу: \( 16 + 139 = 155 \). Ваня выиграл.

Если Петя сделал ход \( (15, S+1) \). Сумма = \( 15 + S + 1 \). Чтобы Петя не выиграл, \( 16 + S < 155 \), то есть \( S < 139 \). Максимальное целое \( S \) равно 138.

Если \( S = 138 \), Петя сделал ход \( (15, 138+1) = (15, 139) \). Сумма = 154. Теперь ход Вани. Ваня может добавить 1 камень в первую кучу: \( 16 + 139 = 155 \). Ваня выиграл.

Таким образом, минимальное значение \( S \), при котором Петя не выигрывает сразу, но Ваня может выиграть своим первым ходом, равно 46.

Ответ: 46