Решение: Подсчёт программ через число 9
Исполнитель Вычислитель преобразует число, записанное на экране. Он умеет выполнять команды: прибавить 1, прибавить 2 и умножить на 3. Программа для Вычислителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений программы содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговТак как все команды увеличивают число, траектория может содержать число 9 только один раз. Поэтому программу можно разделить на путь от 3 до 9 и путь от 9 до 14.
Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для $n$ от 4 до 9 учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3.
$$f(n)=f(n-1)+f(n-2)+[3\mid n]f(n/3)$$Получаем значения: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=3$, $f(7)=5$, $f(8)=8$, $f(9)=14$.
Теперь считаем количество программ от 9 до 14. Получаем: $g(9)=1$, $g(10)=1$, $g(11)=2$, $g(12)=3$, $g(13)=5$, $g(14)=8$.
Общее количество программ равно произведению числа способов пройти обе части пути.
$$14\cdot 8=112$$Где здесь ошибаются
Складывают количество программ вместо перемножения способов пройти две независимые части пути.
Не учитывают команды «прибавить 1» и «прибавить 2» при подсчёте переходов.
Считают траектории, не проходящие через число 9.