Решение: Программы исполнителя М17
Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 1, прибавить 2 и умножить на 3. Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Решение по шагам
5 шаговТак как все команды увеличивают число, сначала траектория проходит через 8, затем через 10.
$$N = N_{2\to 8} \cdot N_{8\to 10} \cdot N_{10\to 12}$$Обозначим через $f(n)$ количество программ, переводящих 2 в $n$. Для чисел от 2 до 8 получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$.
$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{, если }3\mid n$$Из 8 в 10 можно попасть двумя способами: выполнить две команды «прибавить 1» или две команды «прибавить 2»? Первый вариант даёт траекторию 8, 9, 10, второй — 8, 10. Поэтому всего 2 программы.
$$N_{8\to 10}=2$$Из 10 в 12 также есть два способа: 10 → 11 → 12 и 10 → 12.
$$N_{10\to 12}=2$$Перемножаем количество вариантов на трёх участках.
$$N=15\cdot 2\cdot 2=60$$Где здесь ошибаются
Не учитывать обязательный порядок прохождения чисел 8 и 10.
Сложить, а не перемножить количество способов на отдельных участках.
Ошибочно учитывать умножение на 3 там, где оно не приводит к нужному числу.