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

#69451Задание №19ФИПИ

Теория игр

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что произведение количеств камней в кучах будет 144 или больше.

В начальный момент в первой куче был один камень, во второй куче — S камней; $1 \leq S \leq 142 .$

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от дальнейшей игры противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

Пояснение

Решение:

Позицию обозначаем (x, y), а следить будем за произведением $xy$ . Посмотрим, как его меняет ход: $(x+1)y = xy+y \le 2xy$ и $x(y+1) = xy+x \le 2xy$ (ведь $x \ge 1$ и $y \ge 1$ ), а удвоение любой кучи даёт ровно $2xy$ . Значит одним ходом произведение увеличивается не более чем вдвое, и удвоение кучи этот максимум как раз даёт.

Отсюда: игрок заканчивает игру своим ходом тогда и только тогда, когда $2xy \ge 144$ , то есть когда $xy \ge 72$ .

В начальной позиции (1, S) произведение равно $S$ . После хода Пети оно не больше $2S$ , после ответного хода Вани — не больше $4S$ . Значит Ваня способен закончить игру своим первым ходом тогда и только тогда, когда $4S \ge 144$ , то есть при $S \ge 36$ .

Проверим $S = 36$ . Сам Петя не выигрывает: максимум, что он может, — довести произведение до $2\cdot36 = 72$ , а нужно 144. Но если он удвоит вторую кучу, возникнет позиция (1, 72) с произведением 72; Ваня удваивает её ещё раз и получает (1, 144) с произведением 144 — игра закончена, выиграл Ваня.

Проверка перебором:

N = 144

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

def win1(p):                      # ходящий выигрывает первым же ходом
    return any(x * y >= N for x, y in moves(p))

for s in range(1, 143):
    p = (1, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 36
        break

Ответ: 36