Задание 21 ЕГЭ по информатике: стратегия Вани

Условие игры

Два игрока, Петя и Ваня, по очереди делают ходы, первым ходит Петя. Перед ними куча камней. За ход можно добавить в кучу один камень или увеличить число камней в два раза. Игра заканчивается, когда в куче 29 камней или больше. Побеждает тот, кто сделал последний ход. В начале в куче S камней, 1 ≤ S ≤ 28.

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

Разбор

Мы уже знаем: позиции 15–28 выигрышны одним ходом, 14 проигрышна, 7 и 13 выигрышны вторым ходом. Нужна позиция, где любой ход Пети ведёт в 15–28 или в 7 и 13, причём хотя бы один ход ведёт в 7 или 13.

Программа

def f(s, m): if s >= 29: return m % 2 == 0 if m == 0: return False h = [f(s + 1, m - 1), f(s * 2, m - 1)] return any(h) if (m - 1) % 2 == 0 else all(h)

print(min(s for s in range(1, 29) if f(s, 4) and not f(s, 2)))

f(s, 4) значит, что Ваня выигрывает не более чем за два своих хода, not f(s, 2) исключает гарантированный выигрыш первым.

Дерево игры

Иногда в условии просят построить дерево всех партий. Корень это начальная позиция, из неё ветки на все ходы Пети, из каждой ветки ходы Вани по стратегии и так далее до победы. Для S = 12: 12 → 13 → Ваня ходит в 14 → Петя ходит в 15 или 28 → Ваня выигрывает; 12 → 24 → Ваня удваивает и выигрывает.

Проверь себя

• Почему не подходит S = 14? Ответ: из 14 Ваня гарантированно выигрывает первым ходом, а это исключено условием.

Где теряют балл

• Пропущенное «нет стратегии первым ходом». Без этого условия ответом стало бы 14.
• Ход Вани в 14. Из 13 Ваня должен поставить Петю в проигрышную позицию 14, а не выигрывать сразу.

Как тренироваться

Сначала уверенно решайте задание 19 и задание 20. Все номера экзамена в статье ЕГЭ по информатике по номерам.

Частые вопросы