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

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

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

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

Из предыдущего задания мы знаем, что в отрезке значений S [22;42] Петя побеждает первым ходом. Вычислим значения, при которых Ваня побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанный отрезок и отрезок [47-2*S;47-S] – это значение, в котором Ваня выигрывает первым ходом. Распишем значение и стратегии, при которых Ваня побеждает своим первым ходом:

$S = 21$ . Начальная позиция : $(4,21)$ . Петя может сделать следующие позиции: $(5,21),(8,21),(4,22),(4,42)$

Минимальное значение камней в первой куче для того чтобы можно было завершить партию в один ход равняется: $47 − 21 ∗2$ = $5$ .

То есть, если ВСЕ первые ходы Пети во второй куче ведут в отрезок [22;42] и ВСЕ первые ходы в первой куче ведут в отрезок [5;26], тогда это значение, при котором Ваня побеждает первым ходом. Как мы видим, каждое из значение полученное после хода Пети удовлетворяет условию, значит при $S = 21$ Ваня побеждает первым ходом.

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

Если есть хотя бы одна стратегия, которая ГАРАНТИРОВАННО ведет в значение $(5,21)$ для за два хода или в отрезок [47-2*S;47 — S] для первой кучи за два хода, то это значение, при котором Петя побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя побеждает своим вторым ходом:

$S = 19$ . Начальная позиция: $(4;19)$ . Необходимое минимальное значение камней в первой куче для того чтобы завершить партию в один ход равняется $47 − 19∗2 = 9$ . Петя своим ходом сделает следующую позицию: $(8,19)$ . Ваня может сделать позицию $(8,20)$ и проиграет следующим ходом Пети, так как в таком случае минимальное значение камней, при котором игра завершается в один ход равняется: $47− 20 ∗2$ = $7$ . Также Ваня может сделать позицию $(9,19)$ и Петя выиграет после хода $∗2$ для второй кучи $(9;38)$ .

$S = 20$ . Начальная позиция: $(4,20)$ . Петя сделает следующую позицию: $(4,21)$ . Ваня может сделать позиции: $(5,21)$ и тогда Петя победит следующим ходом, либо сделать позицию $(4,22)$ , в которой Пете также не составит труда выиграть патрию следующим ходом.

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

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

from functools import lru_cache

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

Альтернативное решение программой

from functools import lru_cache


def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)


@lru_cache(None)
def game(heap):
    if sum(heap) >= 47:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 43):
    if game((4, s)) == ’P2’:
        print(s)
        break

Ответ: 19