Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — прибавить 2, B — прибавить 3, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 25, при этом траектория вычислений содержит число 15 и не содержит 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 17, 19.
Решение по шагам
4 шагаТак как все команды увеличивают число, в каждой подходящей программе число 15 встречается один раз. Поэтому программу можно разделить на путь от 3 до 15 и путь от 15 до 25.
$$N = N_{3\to15}\cdot N_{15\to25}$$Для первой части применяем динамический подсчёт числа программ, исключая состояние 9. Получаем число допустимых путей от 3 до 15.
Для второй части аналогично подсчитываем все пути от 15 до 25 командами A, B и C.
Перемножая количества вариантов двух частей, получаем число программ.
$$N = 15\cdot 7 = 105$$Где здесь ошибаются
Учитывают программы, в траектории которых встречается число 9.
Не разделяют программу по обязательному промежуточному числу 15.
Складывают количества вариантов вместо их перемножения.