Шешімі: Подсчёт программ Вычислителя
Исполнитель Вычислитель преобразует число на экране. Он выполняет две команды: прибавить 1 и умножить на 2. Программа для Вычислителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21, траектория вычислений содержит число 10 и не содержит числа 18? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Шешім по шагам
4 қадамОбозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Для нечётного $n$ последняя команда может быть только «прибавить 1», а для чётного — также «умножить на 2». Поэтому используем рекуррентное правило.
$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$Последовательно получаем значения: $f(1)=1$, $f(2)=2$, $f(3)=2$, $f(4)=4$, $f(5)=4$, $f(6)=6$, $f(7)=6$, $f(8)=10$, $f(9)=10$, $f(10)=14$.
После достижения числа 10 необходимо попасть в 21, не проходя через 18. Последовательность прибавлений от 10 до 21 невозможна, поскольку содержит 18. Единственный допустимый путь: $10 \to 20 \to 21$.
Каждому из 14 способов достичь числа 10 соответствует ровно один допустимый способ продолжить программу до 21.
$$14\cdot 1=14$$Где здесь ошибаются
Учитывают программы, в которых число 18 встречается до числа 10.
Считают путь последовательного прибавления от 10 до 21 допустимым, хотя он проходит через 18.
Забывают, что после достижения 10 остаётся только один допустимый маршрут до 21.