ВОПРОС 10: Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить один камень в одну из куч и два камня в другую или же увеличить количество камней в любой руче в два раза. Например, пусть в одной куче 6 камней, а в другой 8 камней; такую позицию мы будем обозначать (6, 8). За один ход из позиции (6, 8) можно получить любую из четырёх позиций: (7, 10), (8, 9), (12, 8), (6, 16). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 41 или больше камней. В начальный момент в первой куче было 8 камней, во второй куче S камней, 1 S≤32. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Только один вариант ответа 9 1 16

Решение:

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

Условие задачи:

• Начальная позиция: (8, S), где \( 1 ≤ S ≤ 32 \).
• Ходы:
• Добавить 1 камень в одну кучу и 2 камня в другую: \( (x, y) → (x+1, y+2) \) или \( (x, y) → (x+2, y+1) \).
• Увеличить количество камней в два раза: \( (x, y) → (2x, y) \) или \( (x, y) → (x, 2y) \).
• Победное состояние: \( x + y ≥ 41 \).
• Ваня выиграл своим первым ходом после неудачного первого хода Пети.

Анализ ходов:

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

Пусть начальная позиция (8, S). Петя сделал ход, и получилась позиция \( P \). Ваня сделал ход из позиции \( P \) и выиграл. Чтобы Ваня выиграл своим первым ходом, он должен был попасть в состояние \( ≥ 41 \).

Рассмотрим возможные ходы Пети из (8, S):

1. (8+1, S+2) = (9, S+2)
2. (8+2, S+1) = (10, S+1)
3. (2*8, S) = (16, S)
4. (8, 2*S)

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

Если Петя получил позицию (16, S), то Ваня мог бы сделать ход:

• (16+1, S+2) = (17, S+2): Сумма = \( 19 + S \). Чтобы выиграть, \( 19 + S ≥ 41 \), значит \( S ≥ 22 \).
• (16+2, S+1) = (18, S+1): Сумма = \( 19 + S \). Чтобы выиграть, \( 19 + S ≥ 41 \), значит \( S ≥ 22 \).
• (2*16, S) = (32, S): Сумма = \( 32 + S \). Чтобы выиграть, \( 32 + S ≥ 41 \), значит \( S ≥ 9 \).
• (16, 2*S): Сумма = \( 16 + 2S \). Чтобы выиграть, \( 16 + 2S ≥ 41 \), значит \( 2S ≥ 25 \), \( S ≥ 12.5 \).

Если Петя получил позицию (8, 2S), то Ваня мог бы сделать ход:

• (8+1, 2S+2) = (9, 2S+2): Сумма = \( 11 + 2S \). Чтобы выиграть, \( 11 + 2S ≥ 41 \), значит \( 2S ≥ 30 \), \( S ≥ 15 \).
• (8+2, 2S+1) = (10, 2S+1): Сумма = \( 11 + 2S \). Чтобы выиграть, \( 11 + 2S ≥ 41 \), значит \( 2S ≥ 30 \), \( S ≥ 15 \).
• (2*8, 2S) = (16, 2S): Сумма = \( 16 + 2S \). Чтобы выиграть, \( 16 + 2S ≥ 41 \), значит \( 2S ≥ 25 \), \( S ≥ 12.5 \).
• (8, 2*(2S)) = (8, 4S): Сумма = \( 8 + 4S \). Чтобы выиграть, \( 8 + 4S ≥ 41 \), значит \( 4S ≥ 33 \), \( S ≥ 8.25 \).

Условие задачи: Ваня выиграл своим первым ходом после неудачного первого хода Пети. Это означает, что Петя сделал ход, который не привел к его победе (т.е. сумма камней стала меньше 41), но позволил Ване выиграть следующим ходом.

Для того чтобы Ваня выиграл своим ходом, сумма камней после его хода должна быть \( ≥ 41 \).

Рассмотрим минимальное значение S. Поскольку \( 1 ≤ S ≤ 32 \).

Если S = 9, начальная позиция (8, 9).

Возможные ходы Пети:

• (9, 11) - сумма 20
• (10, 10) - сумма 20
• (16, 9) - сумма 25
• (8, 18) - сумма 26

Все эти позиции меньше 41. Теперь Ваня ходит из одной из этих позиций.

Если Петя сделал ход (16, 9), то Ваня может сделать ход:

• (16+1, 9+2) = (17, 11) - сумма 28
• (16+2, 9+1) = (18, 10) - сумма 28
• (2*16, 9) = (32, 9) - сумма 41. Ваня выиграл!

Таким образом, если S=9, Петя делает ход (16, 9), и Ваня выигрывает ходом (32, 9).

Проверим другие варианты S:

Если S=1, начальная позиция (8, 1).

• Петя: (9, 3) - сумма 12
• Петя: (10, 2) - сумма 12
• Петя: (16, 1) - сумма 17
• Петя: (8, 2) - сумма 10

Из (16, 1) Ваня может сделать:

• (17, 3) - сумма 20
• (18, 2) - сумма 20
• (32, 1) - сумма 33 (не выигрыш)
• (16, 2) - сумма 18

Если S=16, начальная позиция (8, 16).

• Петя: (9, 18) - сумма 27
• Петя: (10, 17) - сумма 27
• Петя: (16, 16) - сумма 32
• Петя: (8, 32) - сумма 40

Из (16, 16) Ваня может сделать:

• (17, 18) - сумма 35
• (18, 17) - сумма 35
• (32, 16) - сумма 48. Ваня выиграл!

Из (8, 32) Ваня может сделать:

• (9, 34) - сумма 43. Ваня выиграл!

Наименьшее значение S, при котором Ваня может выиграть первым ходом после неудачного хода Пети, равно 9.

Ответ: 9