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

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

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

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

Из предыдущего задания мы знаем, что в отрезке [21;62] Петя побеждает своим первым ходом. Для начала нам нужно определить в каких значениях побеждает Ваня своим первым ходом. Если ВСЕ первые ходы Пети ведут в выше описанную область, то данное значение – это значение, при котором Ваня гарантированно побеждает своим первым ходом. Распишем значения и стратегии, при которых Ваня побеждает своим первым ходом:

$S = 19$ , Петя может увеличить количество камней до $21$ или до $57$ , из обоих значений Ваня может победить своим первым ходом.

$S = 20$ , Петя может увеличить количество камней до $22$ или до $60$ , из обоих значений Ваня может победить своим первым ходом.

После того как мы узнали значения, где Ваня побеждает своим первым ходом, мы можем определить значения, при которых Петя побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в значения $19$ или $20$ является значением, где Петя побеждает своим вторым ходом. Минимальное значение S, когда Петя побеждает вторым ходом равно $17$ .

Решение БУ


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

Ответ: 17