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