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

Условие игры

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

Задание 19: известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное S, при котором это возможно.

Разбор позиций

Выигрышные одним ходом позиции: те, из которых можно сразу получить 29 и больше. Удвоение даёт 2S ≥ 29 при S ≥ 15. Значит, при S от 15 до 28 игрок, который ходит, побеждает одним ходом.

Программа для 19–21

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)

f(s, m) отвечает, выигрывает ли нужный игрок не более чем за m ходов от позиции s. Для задания 19 ищем S, у которых есть ход в позицию, где следующий игрок побеждает одним ходом:

print(min(s for s in range(1, 29) if any(f(x, 1) for x in (s + 1, s * 2))))

Проверь себя

• При каких S Петя выигрывает первым ходом? Ответ: от 15 до 28.
• Есть ли у Пети выигрыш первым ходом при S = 14? Ответ: нет, 28 меньше 29.

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

• Граница окончания. «29 или больше» и «больше 29» дают разные позиции.
• Неудачный ход. В задании 19 Петя ошибается, поэтому нужен хотя бы один его ход в выигрышную для Вани позицию, а не все.

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

Продолжение игры: задание 20 и задание 21. Все номера экзамена в статье ЕГЭ по информатике по номерам.

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