19.01 Перекладывание камней одна куча

Решение руками

Для начала определим какие ходы в каких ситуациях мы можем совершать. Изначальное значение S всегда нечётное, также после ходов мы должны получать нечётные значения, значит, в данной игре мы можем использовать только , ходы. Так как, нечётное * нечётное = нечётное число и нечётное + чётное = нечётное число. Теперь определим при каких значениях первым ходом побеждает Петя. Максимальный ход, который мы можем совершить это . Минимальное значение, при котором Петя побеждает своим первым ходом равняется:

Поскольку данное значение чётное, оно нам не подходит. Тогда берём следующее значение и оно уже нам подходит. Получается, что все нечётные значения в отрезке [61;179] - это значения, в которых Петя побеждает своим первым ходом.

Определим значения, при которых Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значения и стратегии, при которых Ваня побеждает первым ходом:

. Петя может увеличить количество камней до ходом или до ходом . В обоих случаях Ване не составит труда завершить партию следующим ходом.

. Петя может увеличить количество камней до ходом или до ходом . В обоих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать наибольшее значение S. Ответ:

Программная реализация

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 180: # если камней в куче стало больше 179
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    if first_heap % 2 == 0: # если количество камней в куче является чётным
        # то можем совершить только +3 ход, так как чётное+нечётное = нечётное
        moves = [game(first_heap+3)]
    else: # если количество камней в куче является нечётным
        # то можем совершить только +4,*3 ход, так как нечётное*нечётное = нечётное и нечётное+чётное = нечётное
        moves = [game(first_heap+4),game(first_heap*3)]
    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(1,180,2):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(i) == -1:
        print(i)

В результате программы на экран будет выведены числа 57 и 59. Наибольшим является число 59.