Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У него есть две команды: прибавить 1 и умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 22 и при этом траектория вычислений содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Шешім по шагам
4 қадамОбозначим через $f(n)$ количество программ перехода из 1 в число $n$. Последняя команда перед получением $n$ либо прибавляет 1, либо умножает число на 2.
$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n$$Последовательно вычисляя значения, получаем количество способов попасть из 1 в 10:
$$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 к 22, не используя числа меньше 10. До числа 20 можно дойти двумя способами: через 19 или командой умножения числа 10 на 2. Поэтому:
$$g(10)=1,\ldots,g(19)=1,\ g(20)=2,\ g(21)=2,\ g(22)=3$$Любая программа, траектория которой содержит 10, однозначно разбивается на участок от 1 до 10 и участок от 10 до 22.
$$14\cdot 3=42$$Где здесь ошибаются
Не учитывают условие прохождения через число 10.
Складывают количество способов вместо умножения.
Разрешают переходы к числам меньше 10 после достижения числа 10.