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

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

Теория игр

Условие игры

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

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

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

Пояснение

Решение:

Как и в предыдущих пунктах, из кучи в $n$ камней ( $n \le 128$ ) ходящий выигрывает одним ходом ровно при $n \ge 65$ , а позиция 64 проигрышна для того, кто из неё ходит: она ведёт только в 65 или 128, откуда соперник побеждает.

Чтобы у Вани вообще была стратегия, Петя не должен выигрывать первым ходом, то есть $S \le 64$ . После хода Пети куча равна $m = S + 1$ или $m = 2S$ , и для каждого из этих двух вариантов Ваня должен побеждать не позже своего второго хода. Это возможно в двух случаях: либо $m \ge 65$ и Ваня выигрывает сразу, либо Ваня может перевести игру в проигрышную позицию 64, то есть $m + 1 = 64$ или $2m = 64$ , что даёт $m = 63$ или $m = 32$ .

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

Перебираем: $2S$ чётно, поэтому равенство $2S = 63$ невозможно, остаётся либо $2S = 32$ (то есть $S = 16$ , но тогда $S + 1 = 17$ не подходит ни под один случай), либо $2S \ge 65$ , то есть $S \ge 33$ . При $S \ge 33$ число $S + 1$ должно быть равно 63 или быть не меньше 65, откуда $S = 62$ или $S \ge 64$ . Значение $S = 64$ отпадает: там оба хода Пети дают 65 и 128, и Ваня выигрывает уже первым ходом, что запрещено вторым условием.

Остаётся $S = 62$ . Проверка: Петя получает 63 или 124. Из 124 Ваня выигрывает сразу удвоением (248), а из 63 сразу выиграть не может (64 и 126 меньше 129), зато ходит в 64, после чего Петя вынужден отдать 65 или 128, и Ваня побеждает вторым ходом.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

def loses(s):        # ходящий из s проигрывает: любой его ход дарит победу сопернику
    return not win_now(s) and all(win_now(m) for m in (s + 1, 2 * s))

for s in range(1, 129):
    if win_now(s):
        continue
    two = all(win_now(m) or loses(m + 1) or loses(2 * m) for m in (s + 1, 2 * s))
    one = all(win_now(m) for m in (s + 1, 2 * s))
    if two and not one:
        print(s)     # 62
        break

Ответ: 62