Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — прибавь 1; B — поменяй местами. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и заменяет число на экране числом, в котором цифры двух младших разрядов поменялись местами. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 101 результатом является число 152?
Решение по шагам
4 шагаВведём $f(n)$ — количество программ, переводящих исходное число 101 в число $n$. Для исходного числа $f(101)=1$.
Переход по команде A возможен из числа $n-1$, поэтому он добавляет $f(n-1)$ способов.
Переход по команде B учитывается для тех чисел, у которых цифра десятков меньше цифры единиц: после перестановки двух последних цифр получается новое достижимое число. Для каждого такого перехода добавляется количество способов достижения исходного числа.
Последовательно перебирая все достижимые числа от 101 до 152 и суммируя количества способов для переходов A и B, получаем $f(152)=42$.
Где здесь ошибаются
Не учитывать условие применимости команды B.
Считать одинаковые последовательности команд одной программой.
Учитывать только последовательное увеличение числа командой A.