Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, позицию (10, 5) можно преобразовать в любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для ходов у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было семь камней, во второй куче — $S$ камней; $1 \le S \le 69$.

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

Accepted Answer

30

Answer

Идея решения: построить рекурсивную функцию, которая проверяет, может ли Ваня выиграть за два своих хода при любых ходах Пети, и отдельно проверить, что Ваня не может выиграть за один ход. Обозначим ходы следующим образом: ход 1 — первый ход Пети, ход 2 — первый ход Вани, ход 3 — второй ход Пети, ход 4 — второй ход Вани. Для проверки условия «Ваня выигрывает первым или вторым ходом» используем функцию, которая: - возвращает 1, если на ходе 4 (второй ход Вани) сумма $\ge 77$; - возвращает 0, если на ходе 4 сумма $< 77$; - на ходах Пети (нечётные) проверяет, что при **всех** его ходах Ваня может выиграть (конъюнкция); - на ходах Вани (чётные) проверяет, что существует **хотя бы один** ход, ведущий к победе (дизъюнкция). Для проверки условия «Ваня не может гарантировано выиграть первым ходом» используем функцию, которая: - возвращает 1, если на ходе 2 (первый ход Вани) сумма $\ge 77$; - возвращает 0, если на ходе 2 сумма $< 77$; - на ходе 1 (первый ход Пети) проверяет, что не при **всех** его ходах Ваня может выиграть первым ходом. ```python def f(x, y, h): # Проверка: Ваня выигрывает первым или вторым ходом if (h == 3 or h == 5) and x + y >= 77: return 1 elif h == 5 and x + y < 77: return 0 elif x + y >= 77 and h < 5: return 0 else: if h % 2 == 0: # Ход Вани: ищем выигрышный ход (дизъюнкция) return (f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1)) else: # Ход Пети: проверяем все его ходы (конъюнкция) return (f(x + 1, y, h + 1) and f(x, y + 1, h + 1) and f(x * 2, y, h + 1) and f(x, y * 2, h + 1)) def f1(x, y, h): # Проверка: Ваня выигрывает первым ходом if h == 3 and x + y >= 77: return 1 elif h == 3 and x + y < 77: return 0 elif x + y >= 77 and h < 3: return 0 else: if h % 2 == 0: # Ход Вани: ищем выигрышный ход (дизъюнкция) return (f1(x + 1, y, h + 1) or f1(x, y + 1, h + 1) or f1(x * 2, y, h + 1) or f1(x, y * 2, h + 1)) else: # Ход Пети: проверяем все его ходы (конъюнкция) return (f1(x + 1, y, h + 1) and f1(x, y + 1, h + 1) and f1(x * 2, y, h + 1) and f1(x, y * 2, h + 1)) # Ищем минимальное S, при котором Ваня выигрывает за два хода for s in range(1, 70): if f(7, s, 1) == 1: # Проверяем, что Ваня не может выиграть за один ход if f1(7, s, 1) == 0: print(s) break ``` Проверим логику для $S = 30$: - Петя может получить позиции: (8, 30), (14, 30), (7, 31), (7, 60). - Из (7, 60) Ваня удваивает вторую кучу: $7 + 120 = 127 \ge 77$ — Ваня выигрывает первым ходом. - Из (14, 30) и (7, 31) Ваня может получить (14, 31). После второго хода Пети возникают позиции (15, 31), (14, 32), (28, 31), (14, 62). Во всех случаях Ваня удваивает вторую кучу и выигрывает вторым ходом. - Из (8, 30) Ваня получает (16, 30). После второго хода Пети возникают позиции (17, 30), (16, 31), (32, 30), (16, 60). Во всех случаях Ваня удваивает вторую кучу и выигрывает вторым ходом. При $S \le 29$ либо Петя выигрывает своим первым или вторым ходом, либо игра не завершится за четыре хода.

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