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