Question

Для игры, описанной в задании 19, найдите два таких минимальных значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Accepted Answer

25 26

Answer

Идея решения: найти позиции, из которых первый игрок не выигрывает сразу, но гарантирует победу на втором ходу, выбирая ход так, чтобы все ответы противника приводили к выигрышным для первого позициям. Обозначим через $A$ множество позиций, при которых первый игрок выигрывает за один ход (вычислено в задании 19). Нужно найти позиции $S otin A$, из которых первый может сделать ход в позицию $T$, такую что при любом ответе второго игрока первый получит позицию из $A$. **Анализ $S = 25$:** Петя может перейти в позиции 27, 28 или 75. - Из 27: Ваня ходит в 29, 30 или 81. Позиция 30 и 81 — выигрышные для Вани (утроение даёт $\geq 89$). Позиция 29 не гарантирует победу Пети на втором ходу. - Из 75: Ваня утраивает и получает 225 — выигрывает сразу. - Из 28: Ваня может получить 30, 31 или 84. Из каждой Петя утраивает: $30 imes 3 = 90 \geq 89$, $31 imes 3 = 93 \geq 89$, $84 imes 3 = 252 \geq 89$. Все позиции выигрышные для Пети. Таким образом, $S = 25$ подходит. **Анализ $S = 26$:** Петя может перейти в позиции 28, 29 или 78. - Из 78: Ваня утраивает и получает 234 — выигрывает сразу. - Из 29: Ваня ходит в 31, 32 или 87. Позиция 87 не гарантирует победу Пети на втором ходу. - Из 28: Ваня может получить 30, 31 или 84. Из каждой Петя утраивает и получает значение $\geq 89$. Таким образом, $S = 26$ подходит. Петя может перейти в позиции 29, 30 или 81. - Из 30: Ваня утраивает и получает 90 — выигрывает сразу. - Из 81: Ваня утраивает и получает 243 — выигрывает сразу. - Из 29: Ваня ходит в 31, 32 или 87. Позиция 87 не гарантирует победу Пети на втором ходу. Позиция $S = 27$ не подходит. Альтернативное решение на Python: ```python def f(x, h): if h == 4 and x >= 89: return 1 elif h == 4 and x < 89: return 0 elif x >= 89 and h < 4: return 0 else: if h % 2 != 0: return (f(x + 2, h + 1) or f(x + 3, h + 1) or f(x * 3, h + 1)) else: return (f(x + 2, h + 1) and f(x + 3, h + 1) and f(x * 3, h + 1)) result = [] for x in range(1, 89): if f(x, 1) == 1: result.append(x) print(result[:2]) ``` Функция `f(x, h)` возвращает 1, если текущий игрок выигрывает из позиции $x$ на ходу $h$. На нечётных ходах (Петя) используется дизъюнкция (достаточно одного выигрышного хода), на чётных (Ваня) — конъюнкция (все ходы должны приводить к выигрышу Пети). Условие $h = 4$ соответствует второму ходу Пети.

Задание №20Алгоритмы и исполнителиЕГЭ по информатике