Решение: Количество программ через число 8
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — вычти 2; B — найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 36 результатом является число 2, и при этом траектория вычислений содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Решение по шагам
4 шагаТак как траектория должна содержать число 8, каждую подходящую программу можно единственным образом разделить на путь от 36 до 8 и путь от 8 до 2.
Обозначим через $f(n)$ количество способов попасть из числа $n$ в 8. Для $n > 8$ используем переходы по командам A и B: $f(n)=f(n-2)+f(\lfloor n/2\rfloor)$, при этом $f(8)=1$. Последовательное вычисление даёт $f(36)=10$.
Обозначим через $g(n)$ количество способов попасть из числа $n$ в 2. При $g(2)=1$ и $g(n)=g(n-2)+g(\lfloor n/2\rfloor)$ получаем $g(8)=4$.
Перемножаем независимые количества вариантов двух частей пути: $10 \cdot 4 = 40$.
Где здесь ошибаются
Не учитывать условие о прохождении через число 8.
Сложить, а не перемножить количество путей от 36 до 8 и от 8 до 2.
Считать число 8 исходным значением, хотя оно должно появиться в траектории после выполнения команды.