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