Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
(А. Рогов) Два игрока, Паша и Витя, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций:
(11, 5), (30, 5), (10, 6), (10, 15). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 60. Если при этом в куче оказалось не более 79 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник, при этом считается, что противник сделал ход.
В начальный момент в первой куче было восемь камней, во второй куче – S камней; 1 ≤ S ≤ 51.
Ответьте на следующие вопросы:
Вопрос 1. Укажите минимальное значение S, при котором Паша не может победить своим первых ходом, но Витя побеждает своим первым ходом при любой игре Паши.
Вопрос 2. Укажите, сколько существует значений S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
– Паша не может выиграть за один ход;
– Паша может выиграть своим вторым ходом независимо от того, как будет ходить Витя.
Вопрос 3. Укажите значение S, при котором одновременно выполняются два условия:
– у Вити есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;
– у Вити нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
(11, 5), (30, 5), (10, 6), (10, 15). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 60. Если при этом в куче оказалось не более 79 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник, при этом считается, что противник сделал ход.
В начальный момент в первой куче было восемь камней, во второй куче – S камней; 1 ≤ S ≤ 51.
Ответьте на следующие вопросы:
Вопрос 1. Укажите минимальное значение S, при котором Паша не может победить своим первых ходом, но Витя побеждает своим первым ходом при любой игре Паши.
Вопрос 2. Укажите, сколько существует значений S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
– Паша не может выиграть за один ход;
– Паша может выиграть своим вторым ходом независимо от того, как будет ходить Витя.
Вопрос 3. Укажите значение S, при котором одновременно выполняются два условия:
– у Вити есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;
– у Вити нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ:
1) 17<br/>2) 3<br/>3) 33
Шаблон решения на 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]}")