Петя и Ваня по очереди ходят в игре с двумя кучами камней. Первым ходит Петя. За один ход игрок может добавить один камень в выбранную кучу или удвоить число камней в ней.
Игра заканчивается, когда сумма камней в двух кучах становится не менее 55. Побеждает тот, кто сделал ход, завершивший игру.
Изначально в первой куче 5 камней, во второй — камней, . Игрок имеет выигрышную стратегию, если может обеспечить победу при любой игре соперника.
Найдите два значения , при которых Петя не может выиграть первым ходом, но гарантированно выигрывает своим вторым ходом. Запишите найденные значения в порядке возрастания.
Решение:
Победу Пети на первом ходу проверяем при x = 2, на втором — при x = 4. На ходах Пети достаточно одного варианта (or), а на ходах Вани должны подойти все варианты (and).
Сдвиг до x = 3 в вызове f оставляет Пете один ход. Так мы исключаем стартовые позиции, где Петя может выиграть сразу.
def f(k1, k2, x):
if x == 4 and (k1 + k2 >= 55): return True
if x == 4 and (k1 + k2 < 55): return False
if (k1 + k2 >= 55): return False
if x % 2 == 1:
return f(k1 + 1, k2, x + 1) or f(k1 * 2, k2, x + 1) or f(k1, k2 + 1, x + 1) or f(k1, k2 * 2, x + 1)
else:
return f(k1 + 1, k2, x + 1) and f(k1 * 2, k2, x + 1) and f(k1, k2 + 1, x + 1) and f(k1, k2 * 2, x + 1)
for k in range(2, 49):
if f(5, k, 1) and not f(5, k, 3):
print(k)
Ответ — 22 24.