Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
**(А. Драганов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит
куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
а) убрать 3 камня или
б) убрать 5 камней или
в) уменьшить количество камней в куче в 2 раза (количество камней в куче, полученное при делении, округляется до большего целого числа).
Выполнять ходы а) и б) можно только тогда, если в куче хватает камней для изъятия. Игра завершается в тот момент, когда в куче останется менее 6 камней. Если при этом в куче окажется нечётное число камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем считается его противник. В начальный момент в куче было S ≥ 6 камней.
Ответьте на следующие вопросы:
Вопрос 1. Укажите максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может гарантированно выиграть, сделав менее двух ходов;
− Петя может гарантированно выиграть, сделав не более двух ходов.
Вопрос 2. Найдите два наименьших значения S, при которых у Вани есть выигрышная стратегия, причём одновременно выполняются два условия:
− Ваня не может гарантированно выиграть, сделав менее двух ходов;
− Ваня может гарантированно выиграть, сделав не более двух ходов.
Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3. У Пети была выигрышная стратегия, придерживаясь которой он мог гарантированно выиграть при любых ходах Вани. Но Петя специально поддался. Петя сделал свой первый ход так, что Ваня сделал только один ход, после которого игра сразу закончилась и Ваня победил. Укажите наименьшее значение S, при котором такое возможно.
куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
а) убрать 3 камня или
б) убрать 5 камней или
в) уменьшить количество камней в куче в 2 раза (количество камней в куче, полученное при делении, округляется до большего целого числа).
Выполнять ходы а) и б) можно только тогда, если в куче хватает камней для изъятия. Игра завершается в тот момент, когда в куче останется менее 6 камней. Если при этом в куче окажется нечётное число камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем считается его противник. В начальный момент в куче было S ≥ 6 камней.
Ответьте на следующие вопросы:
Вопрос 1. Укажите максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может гарантированно выиграть, сделав менее двух ходов;
− Петя может гарантированно выиграть, сделав не более двух ходов.
Вопрос 2. Найдите два наименьших значения S, при которых у Вани есть выигрышная стратегия, причём одновременно выполняются два условия:
− Ваня не может гарантированно выиграть, сделав менее двух ходов;
− Ваня может гарантированно выиграть, сделав не более двух ходов.
Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3. У Пети была выигрышная стратегия, придерживаясь которой он мог гарантированно выиграть при любых ходах Вани. Но Петя специально поддался. Петя сделал свой первый ход так, что Ваня сделал только один ход, после которого игра сразу закончилась и Ваня победил. Укажите наименьшее значение S, при котором такое возможно.
Ответ:
1) 34<br/>2) 19 23<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]}")