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

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

Теория игр

Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 101. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 101 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; $1 \leq S \leq 93 .$
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от дальнейшей игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

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

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

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

Пояснение

Решение:

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

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

$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 = 101

def moves(p):
    a, b = p
    return [(a + 1, b), (2 * a, b), (a, b + 1), (a, 2 * b)]

def over(p):
    return p[0] + p[1] >= 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, 94):
    p = (7, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

S

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

S = 42

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

(7;\ 42)

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

$(8;\ 42)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(16;\ 42)$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(17;\ 42)$ — в $(17;\ 84)$ ; из $(32;\ 42)$ — в $(64;\ 42)$ ; из $(16;\ 43)$ — в $(16;\ 86)$ ; из $(16;\ 84)$ — в $(17;\ 84)$ );
$(14;\ 42)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(14;\ 43)$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(15;\ 43)$ — в $(15;\ 86)$ ; из $(28;\ 43)$ — в $(28;\ 86)$ ; из $(14;\ 44)$ — в $(14;\ 88)$ ; из $(14;\ 86)$ — в $(15;\ 86)$ );
$(7;\ 43)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(14;\ 43)$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(15;\ 43)$ — в $(15;\ 86)$ ; из $(28;\ 43)$ — в $(28;\ 86)$ ; из $(14;\ 44)$ — в $(14;\ 88)$ ; из $(14;\ 86)$ — в $(15;\ 86)$ );
$(7;\ 84)$ — Ваня выигрывает сразу: одним ходом он получает $(7;\ 168)$ , а это уже не меньше 101.

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

Ответ: 42