ЕГЭ · ЗАДАНИЕ 19
Игры: первый ход и смысл стратегии · практика 13
Одна куча содержит S камней, 1≤S<56. Первый ход делает Петя. За ход можно добавить 1 камень(я) или удвоить кучу. Побеждает тот, кто первым получает не менее 56 камней. Найдите минимальное S, при котором Петя не выигрывает первым ходом, но после его неудачного первого хода Ваня может выиграть своим первым ходом.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 14
Решение по шагам
- Выпишем ходы из позиции s: s+1 и 2s. Достижение 56 камней сразу завершает игру.
- W1: есть ход, сразу достигающий цели. L1: немедленно выиграть нельзя, и каждый ход отдаёт сопернику W1. W2: нет победы за один ход, но есть ход в L1.
- В №19 достаточно существования неудачного хода Пети, после которого у Вани есть немедленная победа. Это не означает, что Петя обязан ошибаться.
- Проверяем все S от 1 до 55. Минимальное подходящее S: 14.
| S | После +1 | После ×2 |
|---|---|---|
| 14 | 15 | 28 |
Проверка на Python
T = 56
def moves(s): return (s + 1, s * 2)
def w1(s): return s < T and any(x >= T for x in moves(s))
def l1(s): return s < T and not w1(s) and all(w1(x) for x in moves(s))
def w2(s): return s < T and not w1(s) and any(l1(x) for x in moves(s))
def l2(s):
return (s < T and not w1(s) and not l1(s)
and all(w1(x) or w2(x) for x in moves(s)))
result = [s for s in range(1, T) if not w1(s) and any(w1(x) for x in moves(s))]
print(min(result))