Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 17, при этом траектория вычислений содержит число 9 и не содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
Решение по шагам
5 шаговТак как все команды увеличивают число, число 9 в траектории достигается ровно один раз. Поэтому программы можно разбить на две независимые части: от 2 до 9 и от 9 до 17.
Обозначим через $f(n)$ число программ, переводящих 2 в $n$. Для последнего шага возможны команды A, B и C, поэтому $f(n)=f(n-1)+f(n-2)+f(n/2)$ для чётного $n$, а для нечётного $n$ последнее слагаемое отсутствует.
Последовательно получаем: $f(2)=1$, $f(3)=1$, $f(4)=3$, $f(5)=4$, $f(6)=8$, $f(7)=12$, $f(8)=23$, $f(9)=35$.
Теперь считаем число способов перейти от 9 к 17, не попадая в 12. Значения числа способов для конечных чисел: $g(9)=1$, $g(10)=1$, $g(11)=2$, $g(12)=0$, $g(13)=2$, $g(14)=2$, $g(15)=4$, $g(16)=6$, $g(17)=10$.
Общее число программ равно произведению количества вариантов двух частей: $35\cdot10=350$.
Где здесь ошибаются
Учитывают программы, проходящие через число 12.
Не разбивают траекторию в точке 9.
Забывают, что команда C может быть последним шагом только при чётном конечном числе.