Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он выполняет команды: прибавить 2, прибавить 3 и умножить число на 2. Программа исполнителя — это последовательность команд. Сколько существует программ, которые при исходном числе 3 получают число 25, при этом траектория вычислений содержит число 10 и не содержит число 17? Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Решение по шагам
4 шагаТак как все команды увеличивают число, любую подходящую программу можно однозначно разделить в точке, где впервые получается число 10.
Количество способов получения каждого числа вычисляем рекуррентно: число способов попасть в $x$ равно сумме количеств способов попасть в $x-2$, $x-3$ и $x/2$, если $x$ чётно. При подсчёте программ от 10 до 25 способы, проходящие через 17, не учитываем.
Перемножение количества допустимых программ на первом и втором участках даёт общее число программ.
После выполнения динамического подсчёта получаем $90$ допустимых программ.
Где здесь ошибаются
Учитывают программы, в траектории которых встречается число 17.
Складывают количества программ на участках вместо их перемножения.
Не фиксируют обязательное прохождение через число 10.