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

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

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

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

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

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

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

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

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

$S = 6$ . Петя может увеличить количество камней до $7$ , $12$ или $18$ . В первых двух случаях, Ваня выиграет вторым ходом. В оставшемся случае, Ваня победит первым ходом.

$S = 11$ . Петя может увеличить количество камней до $12$ , $17$ или $33$ . В первом случае, Ваня выиграет вторым ходом. В оставшихся случаях, Ваня победит первым ходом.

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

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

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

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

Определим при каких значениях выигрывает Ваня третьим ходом. Теперь мы знаем, что в значениях $2$ , $5$ , $10$ Петя гарантированно побеждает своим третьим ходом, в значениях $7$ , $12$ Петя гарантированно побеждает своим вторым ходом и в отрезке значений [14;39] Петя побеждает гарантированно своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает третьим ходом, вторым или вторым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает третьим:

$S = 4$ . Петя может увеличить количество камней до $5$ , $10$ , $12$ . В первых двух случаях, Ваня победит третьим ходом. В оставшемся случае, Ваня победит вторым ходом.

$S = 9$ . Петя может увеличить количество камней до $10$ , $15$ , $27$ . В первом случае, Ваня победит третьим ходом. В оставшихся случаях, Ваня победит первым ходом.

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

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

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

В ответ нужно указать сумму значений S, при которых Петя побеждает, не учитывая, значения, в которых Петя побеждает первым ходом. Сумма таких значений S равна: $2 + 3+ 5+ 7+ 8 + 10+ 12 = 47$

Ответ: $47$

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

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

Ответ: 47