Исполнитель Семенова преобразует число, записанное на экране.
У исполнителя есть команды, которым присвоены номера:
1. Прибавить 1,
2. умножить на 2,
3. умножить на 3.
Первая команда увеличивает число на экране на 1, вторая — удваивает число, третья — утраивает число. Программа для исполнителя Семенова — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 38 и при этом траектория вычислений не содержит числа 9 , 24 и 32? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Пусть \(R(n)\) — количество программ, которое число 1 преобразует в число \(n\). Тогда верно следующее утверждение:
\(R(n) = R(n-1)\) — если число не делится ни на 2, ни на 3.
\(R(n) = R(n-1) + R(n:2)\) — если число делится на 2, но не делится на 3.
\(R(n) = R(n-1) + R(n:3)\) — если число делится на 3, но не делится на 2.
\(R(n) = R(n-1) + R(n:2) + R(n:3)\) — если число делится на 2 и на 3.
Заполним таблицу по данным формулам до 8:
\[\begin {array}{|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \text{1}& 2 & 3 & 5 & 5 & 10 & 10 & 15 \\ \hline \end{array}\] Так как по условию сказано, что траектория не должна содержать число 9, значит \(R(9) = 0\). Продолжим заполнять таблицу:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ \hline \text{1}& 2 & 3 & 5 & 5 & 10 & 10 & 15 & 0 & 5 & 5 & 20 & 20 & 30 & 35 & 50 & 50 & 60 & 60 & 70 & 80 & 85 & 85\\ \hline \end{array}\] Аналогично \(R(24) = 0\). Продолжим заполнять таблицу:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{23}& 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31\\ \hline \text{85}& 0 & 0 & 20 & 20 & 50 & 50 & 90 & 90 \\ \hline \end{array}\] Аналогично \(R(32) = 0\). Заполним таблицу до конца:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{31}& 32 & 33 & 34 & 35 & 36 & 37 & 38\\ \hline \text{90}& 0 & 5 & 55 & 55 & 135 & 135 & 195\\ \hline \end{array}\] Отсюда получем ответ — 195
Ответ: 195