Решение: Подсчёт программ Вычислителя
Исполнитель Вычислитель преобразует число на экране. У него есть две команды: «Прибавить 1» и «Умножить на 2». Программа для Вычислителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 30, траектория вычислений содержит число 14 и не содержит число 25? Траектория вычислений программы — это последовательность результатов выполнения всех команд.
Решение по шагам
4 шагаСначала подсчитаем количество программ, переводящих число 2 в число 14. Обозначим это количество через $f(n)$. Для команды «Прибавить 1» используется переход из $n-1$, а для команды «Умножить на 2» — из $n/2$, если $n$ чётно.
$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$Последовательно получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=2$, $f(6)=3$, $f(7)=3$, $f(8)=5$, $f(9)=5$, $f(10)=7$, $f(11)=7$, $f(12)=10$, $f(13)=10$, $f(14)=13$.
Из 14 в 30 можно попасть двумя способами, не посещая число 25: прибавлять 1 до 30 или перейти из 14 в 28 умножением на 2, а затем дважды прибавить 1. Путь через 25 исключается.
$$14\to15\to16\to\ldots\to30;\quad 14\to28\to29\to30$$Выбор пути от 2 до 14 и пути от 14 до 30 независим, поэтому перемножаем количества вариантов.
$$13\cdot2=26$$Где здесь ошибаются
Учитывают программы, в которых число 25 встречается на траектории.
Забывают, что после достижения 14 команды можно продолжать выполнять двумя различными способами.
Складывают, а не перемножают количество вариантов двух частей программы.