Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
(А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч 1 или 2 камня. Игра завершается в тот момент, когда в сумме в кучах будет 13 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 3 камня, во второй – S камней, 1 ≤ S ≤ 9.
Ответьте на следующие вопросы:
Вопрос 1. Петя мог выиграть первым ходом, но сделал неудачный ход и Ваня выиграл. При каком минимальном значении S это возможно?
Вопрос 2. Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.
Вопрос 3. Найдите значение S, при котором Ваня выигрывает вторым ходом при любых ходах Пети.
Ответьте на следующие вопросы:
Вопрос 1. Петя мог выиграть первым ходом, но сделал неудачный ход и Ваня выиграл. При каком минимальном значении S это возможно?
Вопрос 2. Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.
Вопрос 3. Найдите значение S, при котором Ваня выигрывает вторым ходом при любых ходах Пети.
Ответ:
1) 8<br/>2) 5 6<br/>3) 4
Шаблон решения на 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]}")