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

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

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

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

Если такого значения нет, в ответ запишите $0.$

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

Рассмотрим позицию $(9,20)$ :

Если Петя сходит в $(9,10)$ , то Ваня ответит ходом, ведущим в $(9,9)$ , а мы знаем, что Петя проигрывает в этой позиции за один ход;
Если Петя сходит в $(4,20)$ , то Ваня сходит в $(3,20)$ . Из этой позиции Петя никак не выиграет за один ход, а Ваня победит делением второй кучи;
Если Петя сходит в $(8,20)$ , то Ваня сходит в $(8,10)$ . Петя никак не выиграет за $1$ ход, а Ваня выиграет делением второй кучи;
Если Петя сходит в $(9,19)$ , то Ваня сходит в $(9,9)$ . Петя не выигрывает за $1$ ход, а Ваня побеждает делением второй кучи.

Решение Excel

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

Вырежем все значения таблицы (вместе со стартовым, без названий столбцов) и вставим в столбик Петя (первый ход Пети), а после еще три раза вставим табличку в столбик Петя только чуть ниже, чтобы не заходить на значения ранее вставленных табличек.

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

Теперь добавим условное форматирование для первого хода Пети: ячейки сделаем красными (в разделе Главная выберем условное форматирование $⇒$ Правила выделения ячеек $⇒$ Меньше…, в открывшемся окошке записываем $13$ и выбираем красный цвет).

Запишем $9$ в начальную позицию и начнём подставлять значения в ячейку, отвечающую за вторую кучу. Если после одного хода Пети Ваня может победить первым ходом, а после другого Ваня может победить вторым (то есть у Пети не будет красных ячеек после второго хода), то данное значение нам подходит, и его нужно записать в ответ.

Решение программой

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap <= 12:  # Если камней в кучах стало меньше 12
        return 0  # Прекращаем игру
    # Генерация всех возможных ходов
    moves = []
    if second_heap > 1:
        moves.append(game(first_heap, second_heap // 2))
    if first_heap > 1:
        moves.append(game(first_heap // 2, second_heap))
    if first_heap > 0:
        moves.append(game(first_heap - 1, second_heap))
    if second_heap > 0:
        moves.append(game(first_heap, second_heap - 1))
    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(4, 40):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(9,i) == -2:
        print(i)

Ответ: 20