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

#69574Задание №21ФИПИ

Теория игр

Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 161. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу из 161 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 160.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

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

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

Пояснение

Решение:

Напомним условие игры из задания 19. Перед игроками одна куча камней, игроки ходят по очереди, первым ходит Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра заканчивается в тот момент, когда количество камней в куче становится не менее 161; побеждает тот, кто сделал последний ход. В начальный момент в куче $S$ камней, $1 \le S \le 160$ .

Классифицируем позиции (ходит тот, чья очередь):

$W_1$ — ходящий выигрывает своим первым ходом, то есть одним ходом заканчивает игру;
$L_1$ — ходящий сразу выиграть не может, а любой его ход отдаёт сопернику позицию из $W_1$ ; значит, соперник выигрывает своим первым ходом;
$W_2$ — ходящий сразу выиграть не может, но у него есть ход в $L_1$ , поэтому он выигрывает своим вторым ходом;
$L_2$ — ходящий сразу выиграть не может, и каждый его ход ведёт в $W_1$ или в $W_2$ ; значит, соперник выигрывает первым или вторым своим ходом.

Первым ходит Петя, поэтому два условия задачи вместе означают: стартовая позиция принадлежит $L_2$ , но не принадлежит $L_1$ — иначе Ваня гарантированно выигрывал бы первым ходом. Нужно наименьшее такое $S$ . Проще всего перебрать все $S$ программой, вычисляя $W_1$ , $L_1$ , $W_2$ , $L_2$ прямо по этим определениям:

N = 161

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

def over(s):
    return s >= N

def win1(p):                  # ходящий выигрывает своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                 # соперник выигрывает своим первым ходом
    return not win1(p) and all(win1(q) for q in moves(p))

def win2(p):                  # ходящий выигрывает своим вторым ходом
    return not win1(p) and any(lose1(q) for q in moves(p))

def lose2(p):                 # соперник выигрывает первым или вторым ходом
    return not win1(p) and all(win1(q) or win2(q) for q in moves(p))

for s in range(1, 161):
    if lose2(s) and not lose1(s):
        print(s)
        break

Перебор идёт по возрастанию

S

, поэтому первое напечатанное значение и есть минимальное:

S = 78

. Проверим его вручную. Из стартовой позиции

78

Петя может получить:

$79$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $80$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $81$ — в $162$ ; из $160$ — в $161$ );
$156$ — Ваня выигрывает сразу: одним ходом он получает $312$ , а это уже не меньше 161.

Значит, при любой игре Пети Ваня выигрывает первым или вторым ходом. Гарантировать выигрыш именно первым ходом он не может: Пете достаточно сделать тот ход, после которого Ване приходится тратить второй ход. Оба условия выполнены.

Ответ: 78