Задание 21 ЕГЭ: две кучи, особое условие окончания
Две кучи, особое условие окончания: Ваня выигрывает первым или вторым ходом. Тема номера — выигрышная стратегия второго игрока. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.
Пример
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
- добавить в одну из куч (по своему выбору) один камень;
- увеличить количество камней в одной из куч (по своему выбору) в два раза.
Например, пусть в одной куче 20 камней, а в другой 31 камень; такую позицию в игре обозначим (20, 31). Тогда за один ход можно получить любую из четырёх позиций: (21, 31), (20, 32), (40, 31), (20, 62).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 90 или произведение количеств камней в кучах становится не менее 2121. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой выполнено хотя бы одно из этих двух условий. В начальный момент в первой куче было 24 камня, во второй куче – S камней; 1 ≤ S ≤ 65.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите наименьшее значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ
31Решение
Первое условие — f(S, 4): при любой игре Пети Ваня выигрывает не позже своего второго хода. Второе — не f(S, 2): гарантированно выиграть первым ходом Ваня не может (иначе это значение S из задания 19). Нужны S, для которых верно первое и не верно второе.
Проверка для S = 31 (все ходы Пети):
Петя: (25, 31) — одним ходом Ване не выиграть; он ходит в (25, 32), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (48, 31) — Ваня сразу выигрывает ходом в (96, 31);
Петя: (24, 32) — одним ходом Ване не выиграть; он ходит в (25, 32), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (24, 62) — Ваня сразу выигрывает ходом в (48, 62).
Программа: f(p, m) — может ли «наш» игрок выиграть из позиции p не более чем за m полуходов (на нечётном m ходит «наш» игрок — нужен хотя бы один хороший ход, any; на чётном ходит соперник — хорошими должны быть все его ходы, all).
from functools import lru_cache
def moves(p):
a, b = p
return [(a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)]
def done(p):
a, b = p
return a + b >= 90 or a * b >= 2121
@lru_cache(None)
def f(p, m):
if done(p):
return m % 2 == 0
if m == 0:
return False
h = [f(q, m - 1) for q in moves(p)]
return any(h) if m % 2 else all(h)
R = range(1, 66)
print(min(s for s in R if f((24, s), 4) and not f((24, s), 2)))Ответ: 31.