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

Рассмотрим позицию :

1. Если Петя сходит в , то Ваня ответит ходом, ведущим в , а мы знаем, что Петя проигрывает в этой позиции за один ход;
2. Если Петя сходит в , то Ваня сходит в . Из этой позиции Петя никак не выиграет за один ход, а Ваня победит делением второй кучи;
3. Если Петя сходит в , то Ваня сходит в . Петя никак не выиграет за ход, а Ваня выиграет делением второй кучи;
4. Если Петя сходит в , то Ваня сходит в . Петя не выигрывает за ход, а Ваня побеждает делением второй кучи.

Решение Excel

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

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

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

Теперь добавим условное форматирование для первого хода Пети: ячейки сделаем красными (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет).

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

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

from functools import lru_cache


def moves(heap):
    a, b = heap
    m = []
    if a >= 1:
        m += [(a - 1, b), (a // 2, b)]
    if b >= 1:
        m += [(a, b - 1), (a, b // 2)]
    return m


@lru_cache(None)
def game(heap):
    if sum(heap) <= 12:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 3, -1):
    if game((9, s)) == ’V2’:
        print(s)
        break