Решение: Программы с заданной траекторией
Исполнитель преобразует число на экране. У него есть две команды: «Прибавь 2» и «Умножь на 2». Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 52, и при этом траектория вычислений содержит число 18? Траектория вычислений программы — это последовательность результатов выполнения всех команд.
Решение по шагам
4 шагаОбозначим через $f(n)$ количество программ, переводящих исходное число 1 в число $n$. Последняя команда программы может быть «Прибавь 2» или, если $n$ чётно, «Умножь на 2». Поэтому $f(n)=f(n-2)+f(n/2)$ для чётных $n$ и $f(n)=f(n-2)$ для нечётных $n$.
$$f(n)=f(n-2)+\begin{cases}f(n/2),& n\text{ чётно},\\0,& n\text{ нечётно}.\end{cases}$$Последовательно вычисляя значения от 1 до 18, получаем $f(18)=16$. Это число программ, которые переводят 1 в 18.
Теперь считаем число программ от 18 до 52 по той же рекуррентной формуле, положив $g(18)=1$ и $g(n)=0$ для $n<18$. Получаем $g(52)=6$.
Любая программа, траектория которой содержит 18, однозначно состоит из программы от 1 до 18 и программы от 18 до 52. Поэтому количества перемножаются.
$$16\cdot 6=96$$Где здесь ошибаются
Не учитывать обе возможные последние команды при чётном значении.
Сложить, а не перемножить количество программ до 18 и после 18.
Посчитать только программы из 1 в 52, не требуя прохождения через 18.