Задача к ЕГЭ по информатике на тему «Теория игр» №4

Просмотров 9 Комментарии 0

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

Решение руками

Из предыдущей задачи мы знаем, что в значениях $50$ и $59$ Петя побеждает вторым ходом. Значит, если после первого хода в партии в куче будет $50$ или $59$ камней, то Ваня гарантированно победит вторым ходом. Распишем из каких значений можно попасть в $50$ или $59$ :

Из $S = 49$ Петя может попасть либо в $50$ , либо в $59$ . Любой ход из данной позиции приведет Ваню к гарантированному выигрышу своим вторым ходом.

Из $S = 58$ Петя может попасть либо в $59$ , либо в $68$ . Из позиции $68$ Ваня легко выигрывает, добавляя $10$ камней.

При наличии в куче $59$ камней Ване достаточно добавить один камень и получить $60$ камней. Петя сможет увеличить количество камней либо до $61$ , либо до $70$ , откуда Ване достаточно прибавить $10$ к любому из этих значений. Нам нужно взять максимальное значение S. Ответ: $58$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 71: # если камней в куче стало больше 70
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+10)] # прописываем ходы возможные в партии
    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(1,71):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 58