Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У него есть две команды: «Вычти 1» и «Найди целую часть от деления на 2». Первая команда уменьшает число на 1, вторая заменяет число на целую часть от деления числа на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 32 результатом является число 1, и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Решение по шагам
4 шагаОбозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для каждого $n > 1$ последняя команда является либо вычитанием 1, либо делением на 2.
$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$Последовательно вычисляя значения, получаем число программ от 9 до 1:
$$f(2)=2,\ f(3)=3,\ f(4)=5,\ f(5)=7,\ f(6)=10,\ f(7)=13,\ f(8)=18,\ f(9)=23$$Теперь считаем число путей от 32 до 9. Обозначим его через $g(n)$, где $g(9)=1$, а для $n>9$ используем тот же переход.
$$g(n)=g(n-1)+g(\lfloor n/2\rfloor)$$Вычисление от 9 до 32 даёт $g(32)=16$. Каждая программа, проходящая через 9, однозначно составляется из пути от 32 до 9 и пути от 9 до 1.
$$g(32)\cdot f(9)=16\cdot 23=368$$Где здесь ошибаются
Складывают, а не перемножают число путей до 9 и после 9.
Не учитывают все варианты последней команды.
Путают целую часть от деления на 2 с округлением вверх.