21.01 Теория игр
Ошибка.
Попробуйте повторить позже
Для игры, описанной ранее, найдите такое значение , при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если такого значения нет, в ответ запишите .
Решение руками
Рассмотрим и стартовую позицию
.
Если Петя домножит первую кучу на 2 и получит позицию , то Ваня своим первым ходом поставит Петю в
позицию
, увеличив вторую кучу в 2 раза. Из позиции
ни один шаг не приведет Петю к победе (максимальная
сумма, которую может получить Петя, равна
), но любой его шаг ставит Ваню в позицию, из которой Ваня
выигрывает своим вторым ходом, умножив большую кучу на 2.
Если Петя домножит вторую кучу на 2 и получит позицию , то Ваня своим первым ходом поставит Петю в
позицию
, и снова выиграет своим вторым ходом, умножив большую кучу на 2.
Если Петя добавит 1 камень в первую кучу и получит позицию , то Ваня своим первым ходом
поставит Петю в позицию
, увеличив первую кучу в 2 раза. Из позиции
ни один шаг не приведет
Петю к победе (максимальная сумма, которую может получить Петя, равна
), но любой его
шаг ставит Ваню в позицию, из которой Ваня выигрывает своим вторым ходом, умножив большую кучу на
2.
Если Петя добавит 1 камень во вторую кучу и получит позицию , то Ваня своим первым ходом поставит Петю в
позицию
, и снова выиграет своим вторым ходом, умножив большую кучу на 2.
Решение БУ
from functools import lru_cache @lru_cache(None) def game(first_heap, second_heap): # Функция игры if first_heap + second_heap >= 25: # Если камней в куче стало больше 25 return 0 # Прекращаем игру moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap), game(first_heap, second_heap * 2)] # Генерация всех возможных ходов petya_win = [i for i in moves if i <= 0] if petya_win: return -max(petya_win) + 1 # Выигрышный ход Пети else: return -max(moves) # Выигрышный ход Вани # Поиск минимального значения S для выигрыша Вани for s in range(1, 21): if game(4, s) == -2: print(s) # Вывод минимального значения S break
Решение АР
from functools import lru_cache def moves(h): a, b = h return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2) @lru_cache(None) def f(h): if (sum(h) >= 25): return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’P1’ if all(f(x) == ’P1’ for x in moves(h)): return ’V1’ if any(f(x) == ’V1’ for x in moves(h)): return ’P2’ if all(f(x) == ’P1’ or f(x) == ’P2’ for x in moves(h)): return ’V2’ for s in range(1, 21): h = 4, s if f(h) == ’V2’: print(s) break
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!