Решение: Подсчёт программ исполнителя
Исполнитель преобразует число, записанное на экране. Он выполняет команды: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 4 в число 15, если траектория вычислений программы содержит числа 11 и 13? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 7 траектория состоит из чисел 8, 16, 18.
Решение по шагам
5 шаговОбозначим через $f(n)$ количество программ, переводящих число 4 в число $n$. Для последнего шага в число $n$ могли использоваться команды A, B или C, поэтому учитываются переходы из $n-1$, $n-2$ и, если $n$ чётно, из $n/2$.
Последовательно вычисляем значения от 4 до 11:
$$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 можно попасть командами A и B: через 12 или сразу из 11. Поэтому количество программ равно:
$$g(13)=g(12)+g(11)=1+1=2$$Из 13 в 15 также можно попасть через 14 или сразу, поэтому количество программ равно 2.
Так как траектория монотонно возрастает, числа 11 и 13 встречаются именно в таком порядке. Перемножаем количества программ на трёх участках:
$$25\cdot 2\cdot 2=100$$Где здесь ошибаются
Не учитывать обязательный порядок появления чисел 11 и 13.
Считать только один из возможных переходов из 11 в 13 или из 13 в 15.
Сложить количества программ вместо их перемножения.