Решение задачи по теории игр (19, 20)

Решение задач по теории игр (задания 19 и 20). Условие: Две кучи камней. Ходы: +4 камня или в 3 раза больше. Победа: суммарное количество камней \( \ge 98 \). Начало: в первой куче 5 камней, во второй \( S \) камней (\( 1 \le S \le 89 \)). Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Нужно найти минимальное \( S \). Неудачный ход Пети — это такой ход, который подставляет Ваню под победу. Чтобы Ваня выиграл первым ходом, он должен из полученной позиции сделать максимально сильный ход (умножить большую кучу на 3) и получить в сумме 98 или больше. Пусть Петя сделал самый сильный ход из возможных: увеличил вторую кучу в 3 раза. Тогда позиция стала \( (5, 3S) \). Чтобы Ваня выиграл своим первым ходом, он должен из этой позиции сделать еще одно умножение на 3: \[ 5 + 3S \cdot 3 \ge 98 \] \[ 5 + 9S \ge 98 \] \[ 9S \ge 93 \] \[ S \ge 10.33... \] Минимальное целое \( S = 11 \). Проверим: Если \( S = 11 \), начальная позиция \( (5, 11) \). Петя делает неудачный ход: \( (5, 11 \cdot 3) \to (5, 33) \). Ваня делает ход: \( (5, 33 \cdot 3) \to (5, 99) \). Сумма \( 5 + 99 = 104 \ge 98 \). Ваня выиграл. Ответ на задание 19: 11. Задание 20. Найти два наименьших \( S \), при которых у Пети есть выигрышная стратегия: он не может выиграть за 1 ход, но выигрывает вторым ходом при любых ходах Вани. Чтобы Петя выиграл вторым ходом, он должен своим первым ходом создать для Вани такую позицию, из которой любой ход Вани ведет в позицию, где Петя побеждает одним действием. Такая "проигрышная" позиция для Вани должна быть близка к порогу победы, но не позволять ему самому набрать 98. Рассмотрим позицию \( (5, S) \). Петя делает ход в \( (5, S+4) \) или \( (5, 3S) \). Чтобы Петя гарантированно выиграл вторым ходом, он должен передать Ване позицию \( (x, y) \), из которой любой ход Вани дает сумму меньше 98, но позволяет Пете следующим ходом сделать сумму \( \ge 98 \). Обычно такая позиция находится делением границы на 3. Попробуем найти \( S \), при котором Петя может перевести игру в состояние, где сумма камней велика. Если Петя сделает ход в \( (5, 31) \): Ваня может сходить: 1) \( (9, 31) \to \) Петя: \( (9, 31 \cdot 3) = (9, 93) \), сумма 102 (Победа). 2) \( (15, 31) \to \) Петя: \( (15, 31 \cdot 3) = (15, 93) \), сумма 108 (Победа). 3) \( (5, 35) \to \) Петя: \( (5, 35 \cdot 3) = (5, 105) \), сумма 110 (Победа). 4) \( (5, 93) \to \) Петя: \( (5, 93 \cdot 3) = (5, 279) \), сумма 284 (Победа). Во всех случаях Петя выигрывает. Значит, позиция \( (5, 31) \) выигрышная для того, кто в нее ходит. Как Петя может получить \( (5, 31) \)? 1) Если \( S + 4 = 31 \), то \( S = 27 \). 2) Если \( 3S = 31 \) (нет целых решений). Найдем еще одно значение. Попробуем позицию \( (9, 27) \). Если Петя своим первым ходом сделает из \( (5, 27) \) ход \( (9, 27) \): Ваня может: 1) \( (13, 27) \to \) Петя: \( (13, 81) \), сумма 94 (Мало). Значит, \( S = 27 \) подходит только для хода в \( (5, 31) \). Рассмотрим \( S = 23 \). Петя первым ходом делает \( (5, 23+4) = (5, 27) \). Из \( (5, 27) \) Ваня может: 1) \( (9, 27) \to \) Петя: \( (9, 81) \), сумма 90 (Мало). Попробуем другие значения. Для позиции \( (x, y) \) критическая сумма, после которой можно выиграть в 1 ход: \( x + 3y \ge 98 \) или \( 3x + y \ge 98 \). Нам нужно, чтобы после хода Пети Ваня НЕ мог выиграть, а Петя мог. Если Петя делает \( (21, S) \) или \( (5, S+4) \). Проверим \( S = 27 \): Петя ходит в \( (5, 31) \). Ваня: - \( (9, 31) \), сумма 40. Петя: \( 9 + 31 \cdot 3 = 102 \ge 98 \). - \( (15, 31) \), сумма 46. Петя: \( 15 + 31 \cdot 3 = 108 \ge 98 \). - \( (5, 35) \), сумма 40. Петя: \( 5 + 35 \cdot 3 = 110 \ge 98 \). - \( (5, 93) \), сумма 98. Ваня сам выиграл! Значит \( S = 27 \) не подходит, так как Ваня может выиграть. Нужно, чтобы Ваня при любом ходе не получал 98. Максимальный ход Вани из \( (5, S_{new}) \) это \( 5 + 3S_{new} \). Нам нужно \( 5 + 3S_{new} < 98 \), то есть \( 3S_{new} < 93 \), \( S_{new} < 31 \). И при этом Петя должен выиграть своим вторым ходом, значит \( S_{new} \) должно быть достаточно большим. Если Петя делает \( S_{new} = 30 \). Тогда Ваня: - \( (9, 30) \to \) Петя: \( 9 + 30 \cdot 3 = 99 \). - \( (15, 30) \to \) Петя: \( 15 + 30 \cdot 3 = 105 \). - \( (5, 34) \to \) Петя: \( 5 + 34 \cdot 3 = 107 \). - \( (5, 90) \to \) Петя: \( 5 + 90 + 4 = 99 \) (или умножением). Во всех случаях Петя выиграл. Чтобы Петя получил \( S_{new} = 30 \): 1) \( S + 4 = 30 \implies S = 26 \). 2) \( 3S = 30 \implies S = 10 \). Проверим \( S = 10 \): Петя ходит в \( (5, 30) \). Ваня: - \( (9, 30) \), сумма 39. Петя: \( 9 + 90 = 99 \). - \( (15, 30) \), сумма 45. Петя: \( 15 + 90 = 105 \). - \( (5, 34) \), сумма 39. Петя: \( 5 + 102 = 107 \). - \( (5, 90) \), сумма 95. Петя: \( 5 + 90 + 4 = 99 \). Везде Петя выиграл. \( S = 10 \) — первое значение. Проверим \( S = 26 \): Петя ходит в \( (5, 30) \). Ситуация аналогична. \( S = 26 \) — второе значение. Ответ на задание 20: 10 26.