Задание №19: Теория игр: выигрышная стратегия (1 ход)
Основные типы и прототипы задания №19:
Одна куча камней (Победа за 1 ход)
Две кучи камней (Победа Вани за 1 ход)
Условие задания
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 4 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до большего).
Игра завершается, когда количество камней в куче становится не более 3214. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 3214 или менее камней. В начальный момент в куче было S камней, S ≥ 3215. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Укажите сумму значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Вопрос 2. Найдите наименьшее и наибольшее значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Вопрос 3. Найдите количество значений S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
– убрать из кучи 4 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до большего).
Игра завершается, когда количество камней в куче становится не более 3214. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 3214 или менее камней. В начальный момент в куче было S камней, S ≥ 3215. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Укажите сумму значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Вопрос 2. Найдите наименьшее и наибольшее значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Вопрос 3. Найдите количество значений S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ:
1) 38578<br/>2) 9647 28938<br/>3) 8
Решение на Python: Одна куча
from functools import lru_cache def moves(h): return h - 4, h - 5, (h + 2) // 3 @lru_cache(None) def f(h, m): if h <= 3214: return m % 2 == 0 if m == 0: return 0 hod = [f(x, m - 1) for x in moves(h)] if (m - 1) % 2 == 0: return any(hod) return all(hod) S = range(3215, 100000) q1 = [s for s in S if f(s, 2)] print(sum(q1)) q2 = [s for s in S if f(s, 3) and not f(s, 1)] print(min(q2), max(q2)) q3 = [s for s in S if f(s, 4) and not f(s, 2)] print(len(q3))
Этот код разобран по шагам в разборе задания №19: там же типичные ошибки и лайфхаки.