Question

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

Accepted Answer

113 117

Answer

Идея решения: найти позиции, из которых первый игрок не выигрывает за один ход, но может гарантировать победу за два хода, заставляя противника попадать в проигрышные для него позиции. Проанализируем позицию $S = 113$. Петя может перейти в позиции 114, 118 или 452. Позиция 452 — выигрышная для Вани (превышает 473). Позиция 114 не гарантирует победу Пете за второй ход. Петя выбирает позицию 118. Ваня может ответить позициями 119, 123 или 472. Из каждой из этих позиций Петя применяет ход «умножить на 4» и получает значение не менее 476, что превышает 473 — Петя выигрывает. Проанализируем позицию $S = 117$. Петя может перейти в позиции 118, 122 или 468. Позиции 122 и 468 неудачны: из 122 Ваня может перейти в 488 (умножить на 4), из 468 Ваня может перейти в 1872 (умножить на 4) — оба превышают 473, Ваня выигрывает. Петя выбирает позицию 118. Ваня может ответить позициями 119, 123 или 472. Из каждой Петя применяет ход «умножить на 4» и получает значение не менее 476 — Петя выигрывает. Проверим с помощью рекурсивной функции: ```python def f(x, h): if h == 4 and x >= 473: return 1 elif h == 4 and x < 473: return 0 elif x >= 473 and h < 4: return 0 else: if h % 2 != 0: return (f(x + 1, h + 1) or f(x + 5, h + 1) or f(x * 4, h + 1)) else: return (f(x + 1, h + 1) and f(x + 5, h + 1) and f(x * 4, h + 1)) result = [x for x in range(1, 473) if f(x, 1) == 1] print(result[:2]) ``` Функция $f(x, h)$ возвращает 1, если текущий игрок выигрывает при позиции $x$ на ходу $h$. На нечётных ходах (Петя) ищется хотя бы один выигрывающий ход; на чётных ходах (Ваня) проверяется, что все его ходы ведут к выигрышу Пети. Условие $h = 4$ означает второй ход Пети; если $x \geq 473$, Петя выигрывает.

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