Задача #3355

Задания 19–21

Уровень ЕГЭ

Общее условие для 19–21

(О. Лысенков) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

- убрать из первой кучи 5 камней;

- убрать из второй кучи 3 камня;

- уменьшить количество камней в куче в два раза (в случае с первой кучей количество камней, полученное при делении, округляется до меньшего целого, а в случае со второй кучей до большего целого). Например из позиции (41, 23) можно получить позиции (36, 23); (41,20); (20, 23); (41, 12).

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 60. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах суммарно находится 60 камней или меньше.

В начальный момент в первой куче было сто тридцать камней, во второй куче – S камней; 5 ≤ S ≤ 150.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Вопрос для задания 21

Для игры, описанной в задании 19, найдите произведение значений S, при которых одновременно выполняются два условия

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

Задание 19 Задание 20

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

162020880

Общий разбор связки

def g(a,b,m):
    if a + b <= 60: return m % 2 == 0
    if m == 0: return 0
    h = [g(a - 5,b,m - 1),g(a,b - 3,m - 1),g(a // 2,b,m - 1),g(a,b // 2 + b % 2, m - 1)]
    return any(h) if m % 2 else any(h)
print('19)',max(i for i in range(5,151) if g(130,i,2)))

def f(a,b,m):
    if a + b <= 60: return m % 2 == 0
    if m == 0: return 0
    h = [f(a - 5,b,m - 1),f(a,b - 3,m - 1),f(a // 2,b,m - 1),f(a,b // 2 + b % 2, m - 1)]
    return any(h) if m % 2 else all(h)
print('20)',*[i for i in range(5,151) if f(130,i,3) and not  f(130,i,1)][:2])
a = [i for i in range(5,151) if f(130,i,5) and not f(130,i,3)]
pr = 1
for i in a:
    pr *= i
print('21)',pr)

Решение для задания 21

Номер