Петя и Ваня по очереди ходят в игре с двумя кучами камней. Первым ходит Петя. За один ход игрок может добавить один камень в выбранную кучу или удвоить число камней в ней.
Игра заканчивается, когда сумма камней в двух кучах становится не менее 211. Побеждает тот, кто сделал ход, завершивший игру.
Изначально в первой куче 17 камней, во второй — камней, . Игрок имеет выигрышную стратегию, если может обеспечить победу при любой игре соперника.
Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение , при котором это возможно.
Решение:
Победа после первого хода Вани обнаруживается при x = 3. Достаточно одного неудачного хода Пети и одного выигрышного ответа Вани, поэтому на обоих ходах используем or.
def f(k1, k2, x):
if x == 3 and (k1 + k2 >= 211): return True
if x == 3 and (k1 + k2 < 211): return False
if (k1 + k2 >= 211): return False
if x % 2 == 0:
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:
# так как Петя сделал неудачный ход, то тут вместо and нужно тоже писать or.
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)
for k in range(2, 194):
if f(17, k, 1):
print(k)
Ответ — 49.