Решение: Программы с заданной траекторией
Исполнитель Вычислитель преобразует число, записанное на экране. Он выполняет команды: умножить число на 3, прибавить 2 или прибавить 3. Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 15? Траектория вычислений программы — это последовательность результатов выполнения всех команд.
Решение по шагам
4 шагаОбозначим через $f(n)$ количество программ, преобразующих число 2 в число $n$. Для получения $n$ последняя команда могла быть прибавлением 2, прибавлением 3 или умножением на 3.
$$f(n)=f(n-2)+f(n-3)+f(n/3), если n делится на 3$$Последовательно вычисляя значения, получаем количество программ из 2 в 15:
$$f(15)=f(13)+f(12)+f(5)=12+10+1=23$$Теперь считаем количество программ из 15 в 21. Число 21 можно получить из 19 прибавлением 2 или из 18 прибавлением 3. Поэтому таких программ две.
$$g(21)=g(19)+g(18)=1+1=2$$Любая программа, проходящая через 15, однозначно состоит из программы из 2 в 15 и программы из 15 в 21.
$$23\cdot 2=46$$Где здесь ошибаются
Не учитывать условие о прохождении траектории через число 15.
Сложить количество программ вместо перемножения количества вариантов до 15 и после 15.
Учесть умножение на 3 при переходе из 15 в 21, хотя оно даёт число 45.