Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он умеет выполнять команды: $A$ — прибавить 1, $B$ — прибавить 3, $C$ — умножить на 3. Сколько существует программ, которые при исходном числе 3 получают число 20, при этом траектория вычислений содержит число 14 и не содержит число 15? Траектория вычислений — последовательность результатов выполнения всех команд программы.
Шешімін қадамдап көрсету
4 қадамОбозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для последнего шага программы возможны команды $A$, $B$ и $C$, поэтому учитываются переходы из $n-1$, $n-3$ и $n/3$.
$$f(n)=f(n-1)+f(n-3)+f(n/3)$$Последовательно вычисляя значения от 3 до 14, получаем количество программ, переводящих 3 в 14:
$$f(14)=46$$Теперь считаем программы от 14 до 20, не проходящие через 15. Возможны два пути: $14 \to 17 \to 20$ и $14 \to 17 \to 18 \to 19 \to 20$.
$$g(20)=2$$Так как число 14 должно встретиться в траектории, любую подходящую программу можно однозначно разбить на путь от 3 до 14 и путь от 14 до 20.
$$46 \cdot 2=92$$Где здесь ошибаются
Учитывают программы, проходящие через 15.
Забывают, что число 14 должно быть результатом выполнения команды и входить в траекторию.
Складывают количества программ вместо их перемножения.