Решение: Подсчёт траекторий Вычислителя
Исполнитель Вычислитель преобразует число, записанное на экране. У него есть три команды: прибавить 1, прибавить 2 и умножить на 2. Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые исходное число 4 преобразуют в число 13, и при этом траектория вычислений программы содержит число 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд.
Решение по шагам
4 шагаПосчитаем количество программ, переводящих 4 в каждое число до 11. Для числа $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.
$$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(11)=25$.
Из 11 в 13 можно попасть двумя способами: сразу выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
Общее число программ равно произведению количества путей на двух участках.
$$25\cdot 2=50$$Где здесь ошибаются
Не учитывать, что число 11 должно входить именно в траекторию, то есть быть результатом выполнения команды.
Сложить вместо умножения количество путей до 11 и после 11.
Забыть один из двух способов перейти из 11 в 13.