Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1. 2. Умножить на 2. Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решение по шагам
4 шагаОбозначим через $f(n)$ количество программ, переводящих число 2 в число $n$. Для нечётного $n$ последняя команда может быть только «прибавить 1», а для чётного возможны обе команды.
$$f(n)=f(n-1)+f\left(\frac{n}{2}\right)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$Последовательно получаем значения до числа 14: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(6)=3$, $f(8)=5$, $f(10)=7$, $f(12)=10$, $f(14)=13$.
После достижения числа 14 до числа 29 можно пройти только двумя способами: прибавлять по 1 до 29 или выполнить команды «умножить на 2», «прибавить 1», то есть перейти по траектории $14 \to 28 \to 29$.
Так как траектория содержит число 14 ровно один раз, общее количество программ равно произведению количества вариантов двух частей.
$$13\cdot 2=26$$Где здесь ошибаются
Не учитывать, что программа обязательно проходит через число 14.
Сложить, а не перемножить количества вариантов до 14 и после 14.
Посчитать переход из 14 в 29 несколькими умножениями на 2, хотя после умножения число уже превысит 29.