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

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

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

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

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

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

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

Нам подходят $S = 5;6$ . При $5$ Петя сходит в $7$ , прибавлением двух камней в кучу. Далее Ваня либо добавит $2$ камня и станет $9$ камней, либо увеличит кол-во камней в куче в $3$ раза и станет $21$ камень. И из $9$ , и из $21$ Петя выиграет увеличением кол-ва камней в куче в $3$ раза.

В $S = 6$ Петя может увеличить количество камней до $8$ ходом $+ 2$ и далее он гарантированно победит своим вторым ходом.

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

Решение БУ

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

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*3)
@lru_cache(None)
def game(h):
    if h >= 27:
        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, 27):
    if game(s) == ’WIN2’:
        print(s)

Ответ: 6