Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и заменяет число числом, в котором цифры двух младших разрядов поменялись местами. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 100 результатом является число 143?
Шешім по шагам
6 қадамОбозначим через f(n) количество программ, переводящих число 100 в число n. Из 100 можно начать только командой A, поэтому f(100)=1.
Для любого числа n переход по команде A приходит из числа n-1. Дополнительный переход по команде B возможен, если перестановка двух последних цифр числа-источника разрешена.
Последовательно подсчитывая значения, получаем: f(112)=2, f(113)=2, f(114)=2; f(120)=3, f(121)=5, f(122)=5, ..., f(129)=5.
Далее: f(130)=6, f(131)=8, f(132)=13, f(133)=13, ..., f(139)=13.
В число 143 можно попасть командой A из 142 или командой B из 134, поскольку в числе 134 цифра десятков меньше цифры единиц.
Следовательно, f(143)=f(142)+f(134)=21+13=34.
Где здесь ошибаются
Разрешают команду B для чисел, у которых цифра десятков не меньше цифры единиц.
Учитывают только последний переход и не подсчитывают количество программ, приводящих к промежуточным числам.
Забывают, что разные последовательности команд считаются разными программами.