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

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

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

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

Найденные значения запишите в ответе в порядке возрастания без пробела и запятых.

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

Из предыдущих заданий мы знаем, что в значениях $6$ , $9$ , $10$ Петя гарантированно побеждает своим вторым ходом и в отрезке значений [13;24] Петя побеждает гарантированно своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает вторым ходом или первым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает вторым или первым ходом:

При $S = 7$ Петя сходит в $S = 9$ , либо в $S = 14$ . Из $S = 14$ Ваня может прийти в $28$ умножением на $2$ и победить. С $S = 9$ повторится игра из предыдущего задания, только уже по отношению к Ване.

При $S = 8$ Петя сходит в $S = 10$ , либо в $S = 16$ . Из $S = 16$ Ваня выиграет увеличением кол-ва камней в куче в $2$ раза. Из $S = 10$ Ваня придет в $S = 12$ , далее Петя либо добавит $2$ камня, либо увеличит кол-во камней в куче в $2$ раза и станет либо $14$ , либо $24$ камня в куче, тогда Ваня выиграет, умножив кол-во камней в куче на $2$ .

Ответ: $78$

Решение БУ

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

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*2)
@lru_cache(None)
def game(h):
    if h >= 25:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    elif all(game(x) == ’WIN2’ or game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE2’
for s in range(1, 25):
    if game(s) == ’LOSE2’:
        print(s)

Ответ: 78