Решение: Траектории работы Вычислителя
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: 1) прибавить 1, 2) прибавить 2, 3) умножить на 3. Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 13 и при этом траектория вычислений программы содержит число 6? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Решение по шагам
4 шагаПосчитаем количество программ, переводящих число 2 в число 6. Обозначим через f(n) число способов получить n из 2.
$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{ при }3\mid n$$Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=f(5)+f(4)+f(2)=3+2+1=6.
После достижения числа 6 умножение на 3 использовать нельзя, поскольку получится 18, поэтому нужно набрать прибавлениями 7. Число способов представить 7 как сумму единиц и двоек равно 21.
Любая программа, проходящая через 6, однозначно состоит из программы от 2 до 6 и программы от 6 до 13. Поэтому количества перемножаются.
$$6\cdot21=126$$Где здесь ошибаются
Не учитывать программы, в которых число 6 получается командой «умножить на 3».
Сложить, а не перемножить число способов до 6 и после 6.
Разрешить умножение на 3 после получения числа 6, хотя результат 18 превышает 13.