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