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

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

$−$ Петя не может выиграть за один ход;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение БУ

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

Ответ: 617