Петя и Ваня по очереди ходят в игре с двумя кучами. Начинает Петя. За ход можно переложить 3 камня из первой кучи во вторую или добавить 2 камня в первую кучу. Например, из позиции можно перейти в или .
Побеждает тот, после чьего хода произведение размеров куч становится не меньше 600. Изначально в первой куче 40 камней, во второй — , где .
Найдите минимальное , при котором Петя не может выиграть за один ход, а Ваня может выиграть своим первым ходом после любого хода Пети.
Решение:
В условии остановки проверяем произведение k1 * k2. Перекладывание меняет размеры обеих куч за один ход. Запускаем F(40, k, 2): Ваня должен иметь выигрышный ответ на каждый ход Пети.
def F(k1, k2, x):
if k1 * k2 >= 600:
return x % 2 == 0
if x == 0:
return 0
hod = [F(k1 + 2, k2, x - 1)]
if k1 >= 3:
hod.append(F(k1 - 3, k2 + 3, x - 1))
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(1, 15)
if F(40, k, 2)]
print(values[0])
Ответ — 13.
Ответ:
13