ЕГЭ · ЗАДАНИЕ 19
ФИПИ 2027 · задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч (по своему выбору) 4 камня;
– увеличить количество камней в одной из куч (по своему выбору) в 2 раза.
Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (40, 30), (20, 60). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 133. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 133 камня или больше. В начальный момент в первой куче было 17 камней, во второй куче – S камней; 1 ≤ S ≤ 115.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом. Укажите минимальное значение S, при котором такая ситуация возможна.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 29
1. Что означает «такая ситуация возможна»
Достаточно найти один ход Пети, после которого Ваня может закончить игру. Не требуется, чтобы Ваня выигрывал после любого хода Пети. При этом сам Петя своим первым ходом не должен завершить игру.
2. Построим короткий путь к победе
При S = 29: (17, 29) → (17, 58) → (17, 116). Петя удваивает вторую кучу, затем Ваня удваивает её ещё раз. После Пети сумма 75 < 133, после Вани — 133: игра заканчивается.
3. Докажем минимальность
При S ≤ 28 две операции удвоения дают не более max(68 + S, 34 + 2S, 17 + 4S) ≤ 129. Если есть хотя бы одно прибавление 4, максимум ещё меньше: последовательность «+4, ×2» на большей куче даёт не более 17 + 2 × (28 + 4) = 81. Значит за два хода достичь 133 нельзя. Минимальное S = 29.
def moves(a, b):
return [(a+4, b), (a, b+4), (a*2, b), (a, b*2)]
for s in range(1, 116):
if any(sum(p) < 133 and any(sum(v) >= 133 for v in moves(*p))
for p in moves(17, s)):
print(s) # 29
break