19.04 Уменьшение количества камней

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

Для начала найдем значения , при которых Петя мог победить за 1 ход. Чтобы получить число 2, есть всего 4 возможных хода: убрать половину камней, убрать два камня, убрать две трети камней, убрать три камня. Для всех этих ходов подойдут следующие значения Значит нужно рассмотреть только 4 значения и выбрать максимальное, чтобы Ваня мог победить при неудачном ходе Пети. Рассмотрим Первым ходом Петя делает неудачный ход делением на 2 (так как 6 делится на 2) в после чего Ваня например убирает из кучи две трети камней, создавая этим позицию в которой он побеждает.

Решение программой

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    if heap <= 2:  # Если куча меньше или равна 2
        return 0  # Возвращаем стартовое значение 0

    # Список для возможных ходов,
    # которые нужно добавить в зависимости от условий
    steps = []
    # 1 Условие
    if heap % 2 == 0:
        steps += [game(heap // 2)]  # Убираем половину
    else:
        steps += [game(heap - 2)]  # Убираем 2 камня
    # 2 Условие
    if heap % 3 == 0:
        steps += [game(heap // 3)]  # Убрать две трети равносильно оставить одну треть
    else:
        steps += [game(heap - 3)]  # Убираем 3 камня

    petya_win = [x for x in steps if x <= 0]  # Выигрышные позиции для пети

    if petya_win:  # Если такие значения есть
        return -max(petya_win) + 1
    return -max(steps)


for s in range(3, 100):
    if game(s) == 1:  # Если Петя мог победить своим 1ым ходом

        # Для неудачного хода Пети нужно вручную сделать за него ходы от взятого s
        # и запустить функцию с изменнённым значением кучи, чтобы в хотя бы одном из ходов Петя ошибся.
        # Таким образом, Ваня станет первым ходившим игроком для функции,
        # и в итоге нужно будет получить значение 1 для победы Вани первым ходом после неудачного хода Пети.

                                                                                                     
                                                                                                     
        vanya_win = False  # Переменная-флаг, отвечающая за победу Вани (изначально Ваня не побеждает)
        if s % 2 == 0:
            if game(s // 2) == 1:  # Если при ходе //2 в итоге победит Ваня
                vanya_win = True
        else:
            if game(s - 2) == 1:  # Если при ходе -2 в итоге победит Ваня
                vanya_win = True
        if s % 3 == 0:
            if game(s // 3) == 1:  # Если при ходе //3 в итоге победит Ваня
                vanya_win = True
        else:
            if game(s - 3) == 1:  # Если при ходе -3 в итоге победит Ваня
                vanya_win = True

        if vanya_win:  # Если в итоге Ваня победил
            print(s)