Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
(Д. Статный) Снегурочка и Дед Мороз играют в следующую игру: перед ними лежит куча подарков. Игроки ходят по очереди, первый ход делает Снегурочка. За один ход игрок может добавить 2 подарка, 5 подарков, 12 подарков или увеличить их количество в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество подарков. Игра завершается в тот момент, когда суммарное количество подарков станет не менее 121. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в куче будет не меньше, чем 121 подарок. В начальный момент в куче было S подарков; 1 ≤ S ≤ 120. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Дед Мороз выиграл своим первым ходом после неудачного первого хода Снегурочки. Укажите минимальное значение S, когда такая ситуация возможна.
Вопрос 2. Укажите минимальное S, при котором одновременно выполняются два условия:
– у Снегурочки есть выигрышная стратегия, позволяющая ей выиграть своим вторым ходом при любой игре Деда Мороза;
– у Снегурочки нет стратегии, которая позволит её гарантированно выиграть первым ходом.
Вопрос 3. Найдите максимальное и минимальное значения S, при которых
– у Деда Мороза есть выигрышная стратегия, позволяющая ему выиграть, по крайней мере, своим третьим ходом при любой игре Снегурочки;
– у Деда Мороза нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Дед Мороз выиграл своим первым ходом после неудачного первого хода Снегурочки. Укажите минимальное значение S, когда такая ситуация возможна.
Вопрос 2. Укажите минимальное S, при котором одновременно выполняются два условия:
– у Снегурочки есть выигрышная стратегия, позволяющая ей выиграть своим вторым ходом при любой игре Деда Мороза;
– у Снегурочки нет стратегии, которая позволит её гарантированно выиграть первым ходом.
Вопрос 3. Найдите максимальное и минимальное значения S, при которых
– у Деда Мороза есть выигрышная стратегия, позволяющая ему выиграть, по крайней мере, своим третьим ходом при любой игре Снегурочки;
– у Деда Мороза нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Ответ:
1) 31<br/>2) 47<br/>3) 35 46
Шаблон решения на Python
# === Задания 19-21: Теория игр (1 или 2 кучи) ===
def moves(h):
return [h + 1, h * 2]
def game(h):
if h >= 129: return 0 # Победа
next_g = [game(m) for m in moves(h)]
if any(g == 0 for g in next_g): return 1 # Победа 1 ходом (П1)
if all(g == 1 for g in next_g): return 2 # Победа 1 ходом (В1)
if any(g == 2 for g in next_g): return 3 # Победа 2 ходом (П2)
if all(g in (1, 3) for g in next_g): return 4 # Победа 2 ходом (В2)
return -1
for s in range(1, 129):
res = game(s)
if res in (1, 2, 3, 4):
print(f"S={s}: {['П1', 'В1', 'П2', 'В2'][res-1]}")