Решение: Подсчёт программ исполнителя М17
Исполнитель М17 преобразует число, записанное на экране. Он умеет выполнять три команды: прибавить 1, прибавить 2 и умножить на 3. Программа исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 13 и при этом содержат в траектории вычислений оба числа 9 и 11? Траектория вычислений — последовательность результатов выполнения всех команд программы.
Решение по шагам
6 шаговТак как все команды увеличивают число, сначала в траектории встречается 9, затем 11. Поэтому программу можно разделить на три независимых участка.
$$N=N_{3\to9}\cdot N_{9\to11}\cdot N_{11\to13}$$Пусть $f(n)$ — число программ, переводящих число 3 в число $n$. Последней командой могут быть прибавление 1, прибавление 2 или умножение на 3.
$$f(n)=f(n-1)+f(n-2)+f(n/3)$$Последовательно вычисляя значения, получаем число способов попасть из 3 в 9: $f(9)=14$.
Из 9 в 11 можно попасть двумя способами: $+1,+1$ или $+2$.
$$N_{9\to11}=2$$Из 11 в 13 также два способа: $+1,+1$ или $+2$.
$$N_{11\to13}=2$$Перемножаем количества способов для трёх участков.
$$N=14\cdot2\cdot2=56$$Где здесь ошибаются
Не учитывать возможность выполнения команды «Умножить на 3» при подсчёте промежуточных значений.
Сложить количества способов вместо их перемножения.
Учесть только попадание в одно из чисел 9 или 11, а не в оба.