Задача по теме: "Теория игр (Задания 19)"

Решение:

Решим задание через Excel:

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

Подробное решение представлено в файле.

Решим задачу с помощью программы на языке программирования Python:

def game(s, m):
    if s >= 223: return m%2==0
    if m == 0: return 0
    steps = [game(s+4,m-1), game(s+1,m-1), game(s*3,m-1)]
    return any(steps) if m%2!=0 else all(steps)

print('19 задача:', [x for x in range(1,223) if not game(x,0) and game(x,2)])

Данный код решает задачу, используя рекурсивную функцию game(), которая проверяет различные комбинации ходов в игре. Функция game() принимает текущий счет игры s и количество оставшихся ходов m. Если текущий счет s больше или равен 223, функция возвращает True, если m является четным числом, иначе возвращает False. Если количество оставшихся ходов m равно 0, функция возвращает 0. В остальных случаях функция рекурсивно вызывает себя для трех возможных ходов и уменьшает количество оставшихся ходов на 1. Затем функция возвращает True, если хотя бы один из ходов возвращает True (если m нечетное) или если все ходы возвращают True (если m четное). 

Ответ: 74