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

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

В ответе запишите минимальное и максимальное число в порядке возрастания без пробелов и знаков препинаний.

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

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

$S = 24$ . Петя может увеличить количество камней до $27$ или $72$ камней. Ване не составит труда завершить партию следующим ходом.

$S = 25$ . Петя может увеличить количество камней до $28$ или $75$ камней. Ване не составит труда завершить партию следующим ходом.

$S = 26$ . Петя может увеличить количество камней до $29$ или $78$ камней. Ване не составит труда завершить партию следующим ходом.

После того как мы определили значение, при котором Ваня выигрывает своим первым ходом мы можем определить значения, при которых Петя побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведет в $24$ , $25$ или $26$ – это значение, в котором Петя выигрывает вторым ходом. Распишем значение и стратегии, при которых Петя побеждает своим вторым ходом:

$S = 8$ . Петя может увеличить количество камней до $24$ ходом $∗3$ .

$S = 21$ . Петя может увеличить количество камней до $24$ ходом $+ 3$ .

$S = 22$ Петя может увеличить количество камней до $25$ ходом $+ 3$ .

$S = 23$ Петя может увеличить количество камней до $26$ ходом $+ 3$ .

В ответ нужно указать минимальное и максимальное значение S. Ответ: $823$

Решение БУ

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

Решение АР

from functools import lru_cache

def moves(h):
    return (h + 3), (h * 3)

@lru_cache(None)
def game(h):
    if h >= 81:
        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’

for i in range(1, 81):
    if game(i) == ’WIN2’:
        print(i)

Ответ: 823