Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами: A — прибавить 1; B — прибавить 3; C — умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений содержит число 16 и не содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория состоит из чисел 21, 24, 25.
Решение по шагам
4 шагаДля подсчёта числа программ введём $f(n)$ — количество способов получить число $n$ из числа 2. Переходы к числу $n$ могут выполняться командами A, B и C.
$$f(n)=f(n-1)+f(n-3)+\begin{cases}f(n/3),& n\ \text{кратно}\ 3,\\0,&\text{иначе}\end{cases}$$При подсчёте значений до 16 исключаем число 12: количество путей, проходящих через 12, принимаем равным нулю. Получаем последовательность значений от 2 до 16: $1, 1, 1, 2, 4, 5, 7, 12, 17, 24, 0, 17, 41, 43, 60$.
$$f(16)=60$$Из числа 16 в число 20 можно попасть тремя способами: $16\to17\to18\to19\to20$, $16\to17\to19\to20$ и $16\to18\to19\to20$.
$$g(20)=3$$Каждая программа должна сначала попасть в 16, а затем из 16 в 20. Поэтому общее число программ равно произведению количества вариантов двух частей.
$$60\cdot3=180$$Где здесь ошибаются
Не исключают программы, проходящие через число 12.
Считают только один из возможных способов перехода между 16 и 20.
Забывают, что команда C может привести к числу n из числа n/3.