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