Решение: Траектория исполнителя Кантата
Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды: 1) прибавить 1; 2) умножить на 2; 3) умножить на 3. Программа для исполнителя Кантата — это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является число 43 и при этом траектория вычислений содержит число 9, но не содержит число 27? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 16, 48.
Решение по шагам
4 шагаИз числа 5 в число 9 можно попасть только последовательным прибавлением единицы: $5 \to 6 \to 7 \to 8 \to 9$. Поэтому начальный участок программы единственный.
$$N(5 \to 9)=1$$Обозначим через $f(x)$ число способов попасть из 9 в $x$, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.
$$f(x)=f(x-1)+[2\mid x]f\left(\frac{x}{2}\right)+[3\mid x]f\left(\frac{x}{3}\right)$$Так как траектория не должна содержать число 27, полагаем $f(27)=0$. Последовательный подсчёт значений до 43 даёт $f(42)=19$, а поскольку 43 получается из 42 прибавлением 1, $f(43)=19$.
$$f(43)=f(42)=19$$Учитываем единственный способ попасть из 5 в 9.
$$N=1\cdot 19=19$$Где здесь ошибаются
Учитывать программы, в траектории которых встречается число 27.
Забывать, что траектория состоит из результатов после выполнения команд, поэтому число 9 должно быть получено в процессе вычислений.
Не учитывать все три возможные последние команды при подсчёте количества программ.