Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 
камень меньше, чем убирается). При любом из ходов кол-во камней в одной из куч должно измениться. Например, пусть в одной куче будет 
камней, а в другой 
камней; такую позицию мы будем обозначать 
За один ход из позиции 
можно получить любую из четырёх позиций: 
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 
Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 
или менее камней. В начальный момент в первой куче было 
камня, во второй куче 
камней, 
3 » class=»math» width=»auto»>
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение 
при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Решение руками
Очевидно, что при 
Петя выигрывает своим первым ходом (уменьшением кучи, в которой лежит 
камней, в два раза). Значит при 
Петя не сможет победить своим первым ходом, зато это сможет сделать Ваня. Ответ 
.
Решение Excel
Создадим табличку, первый столбец которой назовём Старт, четвёртый Петя, а седьмой — Ваня.
В ячейку 
запишем 
, а в D4 запишем формулу =СУММ(B4:C4).
Так как Ване нужно победить первым ходом, то выгоднее всего ходить самым агрессивным ходом — делением на два. В ячейку 
запишем формулу =ЦЕЛОЕ(МАКС(E4:F4)/2), в 
— =МИН(E4:F4).
В ячейку J4 запишем формулу =СУММ(H4:I4), скопируем и вставим её в следующую клеточку.
В 
запишем =B4-1, в 
=C4, а в 
— =СУММ(E4:F4).
Добавим условное форматирование. Выделим суммы, которые относятся к Пете и затем в разделе Главная выберем условное форматирование 
Правила выделения ячеек 
Меньше…, в открывшемся окошке записываем 
и выбираем красный цвет. Выделим сумму, которая относится к старту, сделаем её зелёной по аналогии с суммой после хода Пети. То же самое сделаем с суммой, которая относится к Ване.
Скопируем полученную таблицу и вставим её три раза, каждый раз чуть ниже предыдущей. Заменим первые ходы Пети, чтобы не было повторов.
В начальную позицию запишем 
и начнём подставлять значения в ячейку 
, пока все суммы камней после хода Вани не станут зелёными.
Решение программой
from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap): # Функция игры
if first_heap + second_heap <= 12: # Если камней в кучах стало меньше 12
return 0 # Прекращаем игру
moves = [game(first_heap, second_heap // 2), game(first_heap // 2, second_heap),
game(first_heap - 1, second_heap),game(first_heap, second_heap - 1)] # Генерация всех возможных ходов
petya_win = [i for i in moves if i <= 0]
if petya_win: # если в данной позиции есть выигрыш Пети
return -max(petya_win) + 1
else: # если в данной позиции выигрыш Вани
return -max(moves)
for i in range(4, 20):
# если в данной позиции возможен выигрыш Вани первым ходом
if game(9,i) == -1:
print(i)
break