Шешімі: Подсчёт программ с числом 11
Исполнитель Вычислитель преобразует число, записанное на экране. Он выполняет три команды: прибавить 2, умножить на 2 и прибавить 3. Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Шешім по шагам
3 қадамПосчитаем количество программ, переводящих число 2 в число 11. Для числа $n$ учитываем последние команды «прибавить 2», «прибавить 3» и, при чётном $n$, «умножить на 2». Получаем $f(11)=10$.
$$f(n)=f(n-2)+f(n-3)+[n\text{ чётно}]f\left(\frac n2\right)$$Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем $g(22)=10$.
Любая подходящая программа однозначно разбивается на часть от 2 до 11 и часть от 11 до 22. Поэтому количества программ перемножаются.
$$10\cdot 10=100$$Где здесь ошибаются
Не учитывать, что число 11 должно входить в траекторию после выполнения команды.
Сложить количества программ вместо их перемножения.
Разрешить переходы через число 11 без фиксации результата 11.