Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
(Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в целое число раз (но не более, чем на 80 камней) или добавить в кучу десять камней или добавить в кучу два камня. Например, из кучи из 10 камней можно получить кучу из 12, 20, 30, 40, 50, 60, 70, 80 и 90 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Выигрывает тот игрок, после хода которого количество камней в куче становится не менее 166.
В начальный момент в куче было S камней; 1 ≤ S ≤ 165. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Петя выиграл своим вторым ходом после неудачного хода Вани. При каком минимальном значении S такое возможно?
Вопрос 2. Известно, что Петя имеет выигрышную стратегию. Укажите минимальное и максимальное значения при которых Петя не может победить первым ходом, но при любом ходе Вани Петя побеждает своим вторым ходом.
Вопрос 3. Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
В начальный момент в куче было S камней; 1 ≤ S ≤ 165. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Петя выиграл своим вторым ходом после неудачного хода Вани. При каком минимальном значении S такое возможно?
Вопрос 2. Известно, что Петя имеет выигрышную стратегию. Укажите минимальное и максимальное значения при которых Петя не может победить первым ходом, но при любом ходе Вани Петя побеждает своим вторым ходом.
Вопрос 3. Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
Ответ:
1) 1<br/>2) 77 153<br/>3) 142
Шаблон решения на 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]}")