20.01 Теория игр

Решение 1

Возможные значения . В каждом из этих случаев Петя не может выиграть первым ходом. При Петя может получить позицию , при — позицию .

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

Решение 2

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 40:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        if a > 1:
            moves.append(f(a // 2 + (a % 2), b))
    if b > 0:
        moves.append(f(a, b - 1))
        if b > 1:
            moves.append(f(a, b // 2 + (b % 2)))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    else:
        return -max(moves)


for i in range(20, 100):
    if f(20, i) == 2:
        print(i)