Разборы · ЕГЭ, задание 19

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

Что проверяет задание

Задания 19, 20 и 21 построены на одной игре: два игрока по очереди добавляют камни в кучи или умножают их, и выигрывает тот, кто первым набрал нужное количество. Каждое задание — отдельный вопрос про эту игру и отдельный 1 балл. Задание 19 — самое простое: обычно нужно найти значение S, при котором игра заканчивается за один-два хода.

Что нужно знать

• Позиция — количество камней в кучах перед ходом. Игра заканчивается, когда выполнено условие (здесь — сумма ≥ 133).
• Выигрышная стратегия — игрок выигрывает при любых ходах соперника.
• В задании 19 часто стратегия не нужна: «Ваня выиграл первым ходом» значит, что Петя мог сходить неудачно. Достаточно, чтобы нашёлся ход Пети, после которого у Вани есть выигрывающий ход.
• Больше всего камней обычно даёт умножение большей кучи.

Как решать

1. Внимательно прочитайте, кто должен выиграть, каким ходом и нужна ли стратегия («при любой игре соперника») или достаточно, что «ситуация возможна».
2. Для простых вопросов хватает рассуждения: какой самый быстрый способ дойти до цели.
3. Проверьте ответ перебором ходов на Python.

Пример из демоверсии 2027

Две кучи камней. За ход можно добавить в одну из куч 4 камня или увеличить одну из куч в 2 раза. Игра заканчивается, когда в двух кучах суммарно не меньше 133 камней. В начале в первой куче 17 камней, во второй — S (1 ≤ S ≤ 115). Первым ходит Петя. Известно, что Ваня выиграл своим первым ходом. Укажите минимальное S, при котором это возможно.

Решение. Самый быстрый рост: Петя удваивает вторую кучу (17, 2S), Ваня удваивает её ещё раз (17, 4S). Нужно 17 + 4S ≥ 133, то есть S ≥ 29. При S = 29 после хода Пети в кучах 17 + 58 = 75 < 133 камней — игра ещё не закончилась. Ответ: 29.

def moves(a, b):
    return [(a + 4, b), (a * 2, b), (a, b + 4), (a, b * 2)]

for S in range(1, 116):
    # есть ход Пети, после которого игра не закончилась,
    # а у Вани есть ход, заканчивающий игру
    if any(x + y < 133 and any(p + q >= 133 for p, q in moves(x, y))
           for x, y in moves(17, S)):
        print(S)                                 # 29
        break

Типичные ошибки

• Ищут выигрышную стратегию Вани, хотя спрашивают, когда его выигрыш возможен.
• Забывают проверить, что после хода Пети игра ещё не закончилась.
• Путают «не менее 133» (≥) и «более 133» (>).

Потренироваться: задание 19 новые варианты с проверкой ответа