21.01 Теория игр

Программное решение

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры

    # Если суммарное кол-во камней в кучах стало более 70
    if first_heap + second_heap > 70:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

    # Если суммарное кол-во камней в кучах стало не менее 50
    if first_heap + second_heap >= 50:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [
        game(first_heap + 1, second_heap),
        game(first_heap * 2, second_heap),
        game(first_heap, second_heap + 1),
        game(first_heap, second_heap * 2)
    ]

    # Находим значения, через которые может победить Петя
    petya_win = [i for i in moves if i <= 0]

    if petya_win:  # Если такие значения нашлись и список не пуст
        return -max(petya_win) + 1
    else:  # Иначе побеждает Ваня максимальным ходом
        return -max(moves)


for S in range(1, 29 + 1):
    # Если в данной позиции Петя гарантированно выигрывает своим вторым ходом
    if game(20, S) == -2:
        print(S)