Решение: Программы с траекторией через 9
Исполнитель Вычислитель преобразует число, записанное на экране. Он умеет выполнять команды: прибавить 1, прибавить 2 и умножить на 3. Программа для Вычислителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 13 и при этом траектория вычислений программы содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Решение по шагам
4 шагаОбозначим через $f(n)$ число программ, переводящих число 1 в число $n$. В число $n$ можно попасть командами «прибавить 1» и «прибавить 2», а также командой умножения на 3, если $n$ делится на 3.
$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/3),& n\mathbin{\vdots}3\\0,& n\text{ не делится на }3\end{cases}$$Последовательно вычисляя значения, получаем: $f(1)=1$, $f(2)=1$, $f(3)=3$, $f(4)=4$, $f(5)=7$, $f(6)=12$, $f(7)=19$, $f(8)=31$, $f(9)=53$.
Количество программ, переводящих 9 в 13, считаем аналогично, не используя значения меньше 9: $g(9)=1$, $g(10)=1$, $g(11)=2$, $g(12)=3$, $g(13)=5$.
Любая программа, проходящая через 9, однозначно распадается на путь от 1 до 9 и путь от 9 до 13. Поэтому количества путей перемножаются.
$$53\cdot 5=265$$Где здесь ошибаются
Считать все программы из 1 в 13, не учитывая обязательное прохождение через 9.
Сложить, а не перемножить количество путей до 9 и после 9.
Разрешить переходы, которые уменьшают число.