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