Задание №20 — Теория игр

#69557Задание №20ФИПИ

Теория игр

Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 19 камней, за один ход можно получить кучу из 20 или 38 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 181. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 181 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 180.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

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

Правильный ответ

45 89

Пояснение

Решение:

Напомним условия игры: перед игроками одна куча камней, за ход можно добавить в кучу один камень или увеличить количество камней вдвое; выигрывает тот, кто первым получит кучу из $181$ камней или больше. Первым ходит Петя, в начале в куче $S$ камней.

Позицию будем оценивать с точки зрения игрока, который ходит из неё. Обозначим: В1 — из позиции можно выиграть первым же ходом; П1 — любой ход не заканчивает игру и переводит соперника в В1 (то есть ходящий проигрывает следующим ходом соперника); В2 — позиция не В1, но есть ход, переводящий соперника в П1, то есть ходящий выигрывает ровно вторым своим ходом при любой игре соперника.

В1. Из кучи в $S$ камней игру заканчивают ходы $S+1 \ge 181$ или $2S \ge 181$ . Второе условие слабее, поэтому В1 — это все $S \ge 91$ .

П1. Нужно, чтобы $S \lt 91$ , но оба хода попадали в В1: $S+1 \ge 91$ и $2S \ge 91$ . Первое неравенство даёт $S \ge 90$ , поэтому единственная позиция П1 — это $S = 90$ (проверка: $2 \cdot 90 = 180 \lt 181$ , игра ещё не окончена).

В2. Петя не выигрывает сразу, но обязан перевести кучу ровно в $90$ камней. Это возможно двумя способами: $S+1 = 90$ , откуда $S = 89$ , и $2S = 90$ , откуда $S = 45$ . Оба значения меньше $91$ , то есть за один ход Петя действительно не выигрывает.

После хода Пети в позицию $90$ Ваня любым ходом получает $91$ или $180$ камней — в обоих случаях игра ещё не окончена, но Петя следующим ходом доводит кучу до $181$ и более ( $91 \cdot 2 = 182 \ge 181$ и $180 + 1 = 181 \ge 181$ ). Это и есть выигрыш вторым ходом.

Тот же ответ даёт короткая программа:

N = 181

def moves(s):
    return [s + 1, 2 * s]

def win1(s):                 # В1: выигрыш своим первым ходом
    return any(t >= N for t in moves(s))

def lose1(s):                # П1: любой ход отдаёт победу сопернику
    return all(t < N and win1(t) for t in moves(s))

def win2(s):                 # В2: выигрыш вторым ходом, но не первым
    return not win1(s) and any(t < N and lose1(t) for t in moves(s))

print(*[s for s in range(1, N) if win2(s)][:2])   # два наименьших

Ответ: 45 89