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

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if (a + b) <= 12:
        return 0
    moves = []
    if a - 2 >= 0:
        moves.append(f(a - 2, b))
    if b - 2 >= 0:
        moves.append(f(a, b - 2))
    if a > 0:
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b // 2))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    return -max(moves)


for i in range(1, 100):
    if i == 1:
        if f(25 - 2, i) == 1 or f(25 // 2, i) == 1 or f(25, i // 2) == 1:
            print(i)
            break
    else:
        if f(25 - 2, i) == 1 or f(25 // 2, i) == 1 or f(25, i // 2) == 1 or f(25, i - 2):
            print(i)
            break

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if (a + b) <= 75:
        return 0
    moves = []
    if a - 3 >= 0:
        moves.append(f(a - 3, b))
    if b - 3 >= 0:
        moves.append(f(a, b - 3))
    if a > 0:
        moves.append(f(a // 5, b))
    if b > 0:
        moves.append(f(a, b // 5))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    return -max(moves)


for i in range(50, 101):
    if f(100, i) == 1:
        print(i)

Решение 1

Петя может выиграть первым ходом, если . Для выигрыша достаточно вдвое уменьшить количество камней во второй куче. При больших значениях за один ход нельзя получить или менее камней в двух кучах.

 

Решение 2

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 40:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        if a > 1:
            moves.append(f(a // 2 + (a % 2), b))
    if b > 0:
        moves.append(f(a, b - 1))
        if b > 1:
            moves.append(f(a, b // 2 + (b % 2)))
    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(20, 100):
    if f(20, i) == 1:
        print(i)

Решение 1

Подпишем ячейки: — , — . Поместим в ячейке число , а наше значение . В ячейке запишем формулу — там будет сумма камней во время старта

В ячейках запишем все возможные пары куч, которые можно получить: в поместим , в — , в поместим (ЦЕЛОЕ возвращает как раз нужный нам результат деления), в — , в поместим , в — , в поместим , в — . В ячейках столбца будем вести сумму куч (в поместим и растянем эту формулу на все пары куч).

В ячейке запишем формулу . Так мы получим сумму куч после самого аргессивного хода Вжика.

Условно окрасим в зеленый цвет ячейку , если значение в ней меньше 35.

Постепенно перебирая значения ячейки от 50 (например) вниз, заметим, что первый раз все ячейки результата выделяются зеленым при . Значит, это максимальное значение, при котором выполняется условие.

Решение 2

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 34:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b - 1))
        moves.append(f(a, b // 2))
    pinki_win = [i for i in moves if i <= 0]
    if pinki_win:
        return -max(pinki_win) + 1
    else:
        return -max(moves)


for i in range(12, 100):
    if f(22, i) == -1:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a <= 11:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1))
    if a > 2:
        moves.append(f(a - 3))
    pupsen_win = [i for i in moves if i <= 0]
    if pupsen_win:
        return -max(pupsen_win) + 1
    return -max(moves)


for i in range(12, 50):
    if f(i - 1) == 1 or f(i - 3) == 1:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, c=0):
    if first_heap + second_heap + third_heap <= 32:
        return 0
    if c > 4:
        return 123123
    moves = []
    if first_heap > 1:
        moves.append(f(first_heap - 1, second_heap, third_heap, c + 1))
        moves.append(f((first_heap + 1) // 2, second_heap, third_heap, c + 1))
    if second_heap > 1:
        moves.append(f(first_heap, second_heap - 1, third_heap, c + 1))
        moves.append(f(first_heap, (second_heap + 1) // 2, third_heap, c + 1))
    if third_heap > 1:
        moves.append(f(first_heap, second_heap, third_heap - 1, c + 1))
        moves.append(f(first_heap, second_heap, (third_heap + 1) // 2, c + 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(11, 100):
    if f(11 - 1, 11, i) == 1 or f((11 + 1) // 2, 11, i) == 1 or f(11, 11-1, i) == 1 or \
            f(11, (11 + 1) // 2, i) == 1 or f(11, 11, i - 1) == 1 or f(11, 11, (i + 1) // 2) == 1:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 32:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        if a > 1:
            moves.append(f(a // 2 + (a % 2), b))
    if b > 0:
        moves.append(f(a, b - 1))
        if b > 1:
            moves.append(f(a, b // 2 + (b % 2)))

    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(22, 100):
    if f(10, i) == -1:
        print(i)

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

Неудачный ход – ход при котором игрок мог победить, но отдал победу противнику. Поэтому для начала найдем значения , при которых Петя мог победить за 1 или 2 хода.

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

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

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 1 камень, – из этой позиции нельзя победить за один ход, поэтому этот вариант не подходит.

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 3 камня, – из этой позиции можно победить за один ход, поэтому этот вариант подходит.

Идея решения:

Мы решаем задачу через моделирование игры с помощью рекурсивной функции. Каждая позиция в игре задаётся числом камней в куче. Если в куче или меньше камней, то игра завершается, и функция возвращает — это означает, что ходящий игрок проигрывает, так как не может больше ходить.

Далее, если в куче больше камней, игрок может сделать один из двух ходов: убрать камень или убрать камня. Мы запускаем функцию рекурсивно для этих новых состояний. Если среди полученных значений есть такие, что противник оказывается в проигрышной позиции (отрицательные или нулевые значения), значит, текущая позиция является выигрышной для игрока, и мы возвращаем положительное число (номер хода, на котором он может выиграть). Если же все возможные ходы ведут к выигрышу противника, то текущая позиция является проигрышной, и возвращаем отрицательное число.

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

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

from functools import lru_cache

@lru_cache(None)
def game(heap):  # Функция игры
    if heap <= 7:  # Если камней в кучах стало меньше 7
        return 0  # Прекращаем игру
    moves = [game(heap - 1), game(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(8, 100):
    if game(i) == 1 or game(i) == 2:  # Если Петя мог победить своим 1ым или 2м ходом

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

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

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

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

Очевидно, что при Петя выигрывает своим первым ходом (уменьшением кучи, в которой лежит камней, в два раза). Значит при Петя не сможет победить своим первым ходом, зато это сможет сделать Ваня. Ответ .

 

Решение 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

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

Для начала найдем значения , при которых Петя мог победить за 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)

Решение руками
Для начала определим значения, из которых Петя выигрывает за один ход. Максимально уменьшить количество камней можно, поделив на , поэтому максимальное значение для победы за один ход равно . Если учитывать округление вниз, числа до также приводят к победе за один ход. Таким образом, при игрок побеждает за один ход. Чтобы Ваня мог выиграть при любом ходе Пети, Петя должен передать Ване выигрышную позицию, то есть все свои ходы должны привести к диапазону . Это возможно при . В ответ записываем минимальное значение , то есть .

Решение программой
Для решения на Python используем рекурсию с проверкой всех возможных ходов, чтобы определить, чья это выигрышная позиция. Функция возвращает , если игра уже завершена (камней ), положительное число – если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник. Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрыш принадлежит Пете, а если отрицательное – Ване. При переборе возможных программа находит три числа S, в ответ записываем минимальное

from functools import lru_cache


@lru_cache(None) # Кэширует предыдущие значения функции, что позволяет ускорить работу программы
def game(first_heap):  # Функция игры
    if first_heap <= 21:  # Если камней в куче стало не более 21
        return 0  # Прекращаем игру
    moves = [game(first_heap - 3), game(first_heap - 7), game(first_heap // 4)]  # Прописываем возможные ходы в партии
    win = [i for i in moves if i <= 0]
    if win:  # Проверяем, есть ли выигрыш в данной позиции
        return -max(win) + 1
    else:  # Если в данной позиции выигрыш соперника
        return -max(moves)


for i in range(22, 100):
    if game(i) == -1:  # Если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение руками
Из предыдущего задания известно, что позиции, из которых Ваня гарантированно выигрывает своим первым ходом, равны . Чтобы Петя мог выиграть своим вторым ходом независимо от действий Вани, хотя бы один его ход должен переводить игру в эти позиции, так что Ваня гарантированно проиграет за один ход. Рассмотрим все возможные ходы Пети: уменьшение на , уменьшение на и деление на с округлением вниз. Тогда получаем:

Следовательно, минимальные значения , при которых Петя выигрывает своим вторым ходом, это и .

Решение программой
Этот код очень похож на реализацию из задачи 19: он также использует рекурсию для проверки всех возможных ходов (, , с округлением вниз) и определяет выигрышные позиции. Отличие лишь в том, что здесь мы ищем значения , при которых Петя выигрывает своим вторым ходом, проверяя game(S) == 2.

from functools import lru_cache


@lru_cache(None) # Кэширует данные, ускоряя работу программы
def game(first_heap):  # Функция игры
    if first_heap <= 21:  # Если камней в куче стало не более 21
        return 0  # Прекращаем игру
    moves = [game(first_heap - 3), game(first_heap - 7), game(first_heap // 4)]  # Прописываем возможные ходы в партии
    win = [i for i in moves if i <= 0]
    if win:  # Проверяем, есть ли выигрыш в данной позиции
        return -max(win) + 1
    else:  # Если в данной позиции выигрыш соперника
        return -max(moves)


for i in range(22, 1000):
    if game(i) == 2:  # Если в данной позиции возможен выигрыш Пети за два хода
        print(i)

Решение руками
Из предыдущих заданий известно, что Петя гарантированно побеждает своим вторым ходом из позиций

а своим первым ходом – из позиций на отрезке . Нам нужно найти минимальное , при котором все ходы Пети переводят игру в эти выигрышные позиции, чтобы Ваня гарантированно выигрывал первым или вторым ходом.

Проверим подряд кандидаты, начиная с .

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

• : после ходов Пети получаем

  

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

Следовательно, минимальное значение , удовлетворяющее требованиям, равно

Решение программой
Этот код почти идентичен реализации из задачи 19, а единственное отличие заключается в условии проверки в цикле: здесь проверяется game(S) == -2, что соответствует поиску начальных значений , из которых Ваня выигрывает первым или вторым ходом.

from functools import lru_cache


@lru_cache(None) # Кэширует данные, ускоряя работу программы
def game(first_heap):  # Функция игры
    if first_heap <= 21:  # Если камней в куче стало не более 21
        return 0  # Прекращаем игру
    moves = [game(first_heap - 3), game(first_heap - 7), game(first_heap // 4)]  # Прописываем возможные ходы в партии
    win = [i for i in moves if i <= 0]
    if win:  # Проверяем, есть ли выигрыш в данной позиции
        return -max(win) + 1
    else:  # Если в данной позиции выигрыш соперника
        return -max(moves)


for i in range(22, 1000):
    if game(i) == -2:  # Если в данной позиции возможен выигрыш Вани за один или два хода
        print(i)

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

Поймём, что значение - победа Пети, ведь он сразу может вычесть .

Значение не делится на , значит можно вычесть и получить победу Пети.

Значение не делится на , значит можно вычесть и получить победу Пети.

Значение не делится на , значит можно вычесть и получить , из которого сможет выиграть Ваня. Если вычесть , то из можно получить аналогично прошлым шагам, Ваня победит. Значение не делится на , вычитаем , а из Ваня вновь сможет одержать победу. При всех трёх значениях Петя никак не может выиграть.

Ответ:

Решение программой:
Для решения на Python используем рекурсию с проверкой всех возможных ходов (, делить на , делить на ), чтобы определить, чья это выигрышная позиция.
Функция возвращает , если игра уже завершена (камней ), положительное число — если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник.
Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрывает Петя, а если отрицательное – Ваня. Если функция вернёт - значит Петя гарантированно проиграл первым ходом, а Ваня выиграл. При переборе возможных начальных значений программа выводит .

# lru_cache позволит сэкономить ресурсы компьютера. Функция будет сохранять прошлые значения функций, а значит не придётся считать из заново.
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
    if first_heap <= 19: # Если камней в куче стало меньше или равно 19
        return 0 # Прекращаем игру
    if first_heap % 3 == 0: # Занесём в b значение функции исходя из кратности числа (по условию)
        b = game(first_heap // 3)
    else:
        b = game(first_heap - 2)
    if first_heap % 5 == 0: # Занесём в с значение функции исходя из кратности числа (по условию)
        c = game(first_heap // 5)
    else:
        c = game(first_heap - 3)
    moves = [game(first_heap - 1), b, c] # Прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1 # От лица Пети будет выигрыш (положительное число, прибавляем 1, поскольку это будет уже следующий ход)
    else: # Если в данной позиции выигрыш Вани
        return -max(moves) # От лица Пети будет проигрыш (отрицательное число)

for i in range(20, 100): # Переберём возможные значения (единицу не берём из-за возведения в квадрат, ведь программа будет бесконечной)
    if game(i) == -1: # Если в данной позиции возможен выигрыш Вани вторым ходом
        print(i) # Выведем нужное значение

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

Поймём, что значение - победа Пети, ведь он сразу может вычесть .

Значение не делится на , значит можно вычесть и получить победу Пети.

Значение делится на , значит можно поделить и получить победу Пети.

Значение делится на , значит можно поделить и получить победу Пети.

Значение не делится на , значит можно вычесть и получить , из которого сможет выиграть Ваня (). Если вычесть , то из можно получить , Ваня победит. Значение не делится на , вычитаем , а из Ваня вновь сможет одержать победу (). При всех трёх значениях Петя никак не может выиграть.

Ответ:

Решение программой:
Для решения на Python используем рекурсию с проверкой всех возможных ходов (, делить на , делить на ), чтобы определить, чья это выигрышная позиция.
Функция возвращает , если игра уже завершена (камней ), положительное число — если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник.
Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрывает Петя, а если отрицательное – Ваня. Если функция вернёт - значит Петя гарантированно проиграл первым ходом, а Ваня выиграл. При переборе возможных начальных значений программа выводит .

# lru_cache позволит сэкономить ресурсы компьютера. Функция будет сохранять прошлые значения функций, а значит не придётся считать из заново.
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
    if first_heap <= 17: # Если камней в куче стало меньше или равно 17
        return 0 # Прекращаем игру
    if first_heap % 3 == 0: # Занесём в b значение функции исходя из кратности числа (по условию)
        b = game(first_heap // 3)
    else:
        b = game(first_heap - 2)
    if first_heap % 5 == 0: # Занесём в с значение функции исходя из кратности числа (по условию)
        c = game(first_heap // 5)
    else:
        c = game(first_heap - 3)
    moves = [game(first_heap - 1), b, c] # Прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1 # От лица Пети будет выигрыш (положительное число, прибавляем 1, поскольку это будет уже следующий ход)
    else: # Если в данной позиции выигрыш Вани
        return -max(moves) # От лица Пети будет проигрыш (отрицательное число)

for i in range(20, 100): # Переберём возможные значения (единицу не берём из-за возведения в квадрат, ведь программа будет бесконечной)
    if game(i) == -1: # Если в данной позиции возможен выигрыш Вани вторым ходом
        print(i) # Выведем нужное значение

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

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

Если попалось число не кратное двум и пяти, то игрок обязан вычесть один камень, сделав число как минимум чётным.

Тогда сделаем действия в обратном порядке. Больше всего камней отнимает деление на два, будем делать его от максимального числа для выигрыша - .

. Значит из 18 Ваня смог бы моментально выиграть. Остаётся добавить единицу, ведь у Пети просто не будет выбора.

Число определённо нам подходит. Петя уменьшит его на единицу, а Ваня поделит на , выиграв первым ходом.

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

Ответ:

Решение программой:
Для решения на Python используем рекурсию с проверкой всех возможных ходов (, делить на , делить на ), чтобы определить, чья это выигрышная позиция.
Функция возвращает , если игра уже завершена (камней ), положительное число — если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник.
Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрывает Петя, а если отрицательное – Ваня. Если функция вернёт - значит Ваня гарантированно выиграл первым ходом. При переборе возможных начальных значений программа выводит максимум .

# lru_cache позволит сэкономить ресурсы компьютера. Функция будет сохранять прошлые значения функций, а значит не придётся считать из заново.
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
    b = 100000000000000000000000000  # В b и c будут записаны результаты определённых ходов, если они возможны
    c = 100000000000000000000000000
    if first_heap <= 9: # Если камней в куче стало меньше или равно 9
        return 0 # Прекращаем игру
    if first_heap % 3 == 0: # Занесём в b значение функции исходя из кратности числа (по условию)
        b = game(first_heap * 2 // 3) # Уберём треть числа
    if first_heap % 2 == 0: # Занесём в с значение функции исходя из кратности числа (по условию)
        c = game(first_heap // 2)
    moves = [game(first_heap - 1)] # Прописываем ходы возможные в партии
    if b != 100000000000000000000000000:
        moves.append(b)
    if c != 100000000000000000000000000:
        moves.append(c)
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1 # От лица Пети будет выигрыш (положительное число, прибавляем 1, поскольку это будет уже следующий ход)
    else: # Если в данной позиции выигрыш Вани
        return -max(moves) # От лица Пети будет проигрыш (отрицательное число)

for i in range(10, 1000): # Переберём возможные значения (единицу не берём из-за возведения в квадрат, ведь программа будет бесконечной)
    if game(i) == -1: # Если в данной позиции возможен выигрыш Вани первым ходом
        print(i) # Выведем нужное значение

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

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

Если попалось число не кратное двум и пяти, то игрок обязан вычесть один камень, сделав число как минимум чётным.

Тогда сделаем действия в обратном порядке. Больше всего камней отнимает деление на два, будем делать его от максимального числа для выигрыша - .

. Значит из 22 Ваня смог бы моментально выиграть. Остаётся добавить единицу, ведь у Пети просто не будет выбора.

Число определённо нам подходит. Петя уменьшит его на единицу, а Ваня поделит на , выиграв первым ходом.

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

Ответ:

Решение программой:
Для решения на Python используем рекурсию с проверкой всех возможных ходов (, делить на , делить на ), чтобы определить, чья это выигрышная позиция.
Функция возвращает , если игра уже завершена (камней ), положительное число — если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник.
Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрывает Петя, а если отрицательное – Ваня. Если функция вернёт - значит Ваня гарантированно выиграл первым ходом. При переборе возможных начальных значений программа выводит максимум .

# lru_cache позволит сэкономить ресурсы компьютера. Функция будет сохранять прошлые значения функций, а значит не придётся считать из заново.
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
    b = 100000000000000000000000000  # В b и c будут записаны результаты определённых ходов, если они возможны
    c = 100000000000000000000000000
    if first_heap <= 11: # Если камней в куче стало меньше или равно 11
        return 0 # Прекращаем игру
    if first_heap % 3 == 0: # Занесём в b значение функции исходя из кратности числа (по условию)
        b = game(first_heap * 2 // 3) # Уберём треть числа
    if first_heap % 2 == 0: # Занесём в с значение функции исходя из кратности числа (по условию)
        c = game(first_heap // 2)
    moves = [game(first_heap - 1)] # Прописываем ходы возможные в партии
    if b != 100000000000000000000000000:
        moves.append(b)
    if c != 100000000000000000000000000:
        moves.append(c)
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1 # От лица Пети будет выигрыш (положительное число, прибавляем 1, поскольку это будет уже следующий ход)
    else: # Если в данной позиции выигрыш Вани
        return -max(moves) # От лица Пети будет проигрыш (отрицательное число)

for i in range(10, 1000): # Переберём возможные значения (единицу не берём из-за возведения в квадрат, ведь программа будет бесконечной)
    if game(i) == -1: # Если в данной позиции возможен выигрыш Пети первым ходом
        print(i) # Выведем нужное значение