Решение: Программы исполнителя К17
Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 1, прибавить 2 и умножить на 2. Программа для исполнителя К17 — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 3 в число 13 и при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна содержать оба указанных числа. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Решение по шагам
5 шаговПоскольку каждая команда увеличивает число, программа, содержащая в траектории числа 9 и 11, сначала должна попасть в 9, затем в 11.
Посчитаем динамически число способов попасть из 3 в каждое число с помощью команд «+1», «+2» и «×2». Для чисел от 3 до 9 получаем: $1, 1, 2, 4, 6, 11, 17$. Значит, $N(3 \to 9)=17$.
$$N(x)=N(x-1)+N(x-2)+[x\ \text{чётно}]N\left(\frac{x}{2}\right)$$Из 9 в 11 можно попасть двумя способами: $9\to10\to11$ и $9\to11$.
$$N(9 \to 11)=2$$Из 11 в 13 также существует два способа: $11\to12\to13$ и $11\to13$.
$$N(11 \to 13)=2$$Перемножаем количество вариантов на трёх независимых участках траектории.
$$17\cdot2\cdot2=68$$Где здесь ошибаются
Не учитывать, что числа 9 и 11 должны встречаться в траектории в указанном порядке.
Сложить количество программ вместо перемножения вариантов на отдельных участках.
Посчитать программы, которые достигают 13, но не проходят через оба обязательных числа.