Решение: Подсчёт программ исполнителя К17
Исполнитель К17 преобразует число, записанное на экране. Он выполняет команды: прибавить 1, прибавить 2 или умножить на 2. Программа — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 13 и при этом траектория вычислений содержит оба числа 10 и 12? Траектория вычислений — последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория состоит из чисел 8, 16, 18.
Решение по шагам
5 шаговСначала подсчитаем количество программ, переводящих число 4 в число 10. Обозначим через f(n) число способов получить n из 4.
$$f(n)=f(n-1)+f(n-2)+f(n/2)\text{ при чётном }n$$Последовательно получаем: f(4)=1, f(5)=1, f(6)=2, f(7)=3, f(8)=6, f(9)=9, f(10)=16.
$$f(10)=f(9)+f(8)+f(5)=9+6+1=16$$Из 10 в 12 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
$$N_{10\to12}=2$$Из 12 в 13 существует только один способ — прибавить 1.
$$N_{12\to13}=1$$Так как траектория должна содержать 10 и 12, количество программ равно произведению количеств способов на трёх участках.
$$N=16\cdot2\cdot1=32$$Где здесь ошибаются
Не учитывать, что траектория должна содержать оба числа — 10 и 12.
Сложить количества способов вместо их перемножения.
Учесть переходы, которые превышают число 13.