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

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

Теория игр

Условие игры

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

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

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

55 56

Пояснение

Решение:

Напомним игру: позиция (x, y) — две кучи; своим ходом игрок добавляет в одну из куч два камня либо удваивает одну из куч; игра заканчивается, когда в кучах суммарно окажется не менее 118 камней. В начале первая куча — 3 камня, вторая — S камней.

За один ход сумма растёт на 2, на x или на y, значит игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+\max(x,\,y,\,2) \ge 118$ . В интересующих нас позициях вторая куча больше, поэтому условие принимает вид $x+2y \ge 118$ .

Чтобы выиграть вторым ходом, Петя должен передать Ване проигрышную позицию: из неё Ваня закончить игру не может, но любой его ход отдаёт победу Пете. Слабейший ход Вани — «+2» в первую кучу, после него нужно $x+2+2y \ge 118$ , то есть $x+2y \ge 116$ ; а чтобы сам Ваня не выиграл, нужно $x+2y \le 117$ . Итак, проигрышные позиции — те, где $x+2y$ равно 116 или 117 (остальные ходы Вани увеличивают сумму ещё сильнее, так что после них Петя тем более заканчивает игру).

S = 55. Позиция (3, 55): $3+2\cdot 55 = 113 \lt 118$ — сам Петя не выигрывает. Он добавляет два камня во вторую кучу: (3, 57), где $3+2\cdot 57 = 117$ . Любой ответ Вани проигрышен: (5, 57) даёт $5+114=119$ , (3, 59) даёт $3+118=121$ , (6, 57) даёт $6+114=120$ , (3, 114) — тем более; во всех случаях Петя своим вторым ходом удваивает бо́льшую кучу и набирает не менее 118 камней. (Годится и ход «удвоить первую кучу»: (6, 55), где $6+110=116$ .)

S = 56. Позиция (3, 56): $3+112=115 \lt 118$ . Петя добавляет два камня в первую кучу: (5, 56), где $5+2\cdot 56 = 117$ — снова проигрышная позиция. Другие ходы не годятся: после (3, 58) получается $3+116=119$ , после (6, 56) — $6+112=118$ , то есть Ваня выигрывает сразу; ход (3, 112) очевидно проигрышный.

Меньших значений нет, что подтверждает перебор:

N = 118
A = 3                             # камней в первой куче

def moves(p):
    x, y = p
    return [(x + 2, y), (x, y + 2), (2 * x, y), (x, 2 * y)]

def win1(p):                      # ходящий заканчивает игру своим ходом
    return any(x + y >= N for x, y 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))

print([s for s in range(1, 114) if win2((A, s))][:2])   # [55, 56]

Ответ: 55 56