Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число, записанное на экране. У него есть три команды: 1) прибавить 1; 2) прибавить 2; 3) умножить на 3. Сколько существует программ, которые преобразуют исходное число 2 в число 13 и при этом траектория вычислений содержит числа 9 и 11? Траектория должна содержать оба указанных числа. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Шешім по шагам
5 қадамПоскольку все команды увеличивают число, числа 9 и 11 в траектории могут встретиться только в порядке $9$, затем $11$.
Посчитаем количество программ из 2 в каждое число до 9. Для числа $n$ учитываем переходы из $n-1$, из $n-2$ и, если $n$ кратно 3, из $n/3$.
$$f(2)=1,\ f(3)=1,\ f(4)=2,\ f(5)=3,\ f(6)=6,\ f(7)=9,\ f(8)=15,\ f(9)=15+9+1=25$$Из 9 в 11 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
$$N_{9\to11}=2$$Из 11 в 13 также существует два способа: «прибавить 2» или дважды «прибавить 1».
$$N_{11\to13}=2$$Перемножаем количества независимых участков траектории.
$$25\cdot2\cdot2=100$$Где здесь ошибаются
Забывают, что умножение на 3 может быть последней командой на участке, например переход $3\to9$.
Учитывают порядок $11$ перед $9$, хотя все команды только увеличивают число.
Не перемножают количества способов построения отдельных участков траектории.