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

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

Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполяняются два условия:

$−$ у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

$−$ у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Нам нужно найти такое значение камней во второй куче, при котором Ваня выиграет своим вторым ходом. Петя проиграет независимо какие ходы он будет делать, он проиграет быстрее если будет делать ход $∗ 4$ , потому он будет делать ход $+ 2$ , чтобы максимально затянуть партию.

Получается, первые $3$ хода в партии будут ходы $+ 2$ для первой кучи камней, а на своем втором ходу Ваня умножит вторую кучу на $4$ .

Нам известно, что изначально в первой куче было $4$ камня, после трёх ходов в первой куче будет $10$ камней. Условием выигрыша является суммарное количество камней равное или больше $94$ камней. Получаем, что $94$ — $10 = 84$ (столько камней будет во 2-ой куче в конце партии).

Значит, в начале партии во второй куче было: $84 : 4 = 21$ камней. Ответ: $21$

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

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

Ответ: 21