Исполнитель РЫБИНСК преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя РЫБИНСК — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-2)\)
Заполним таблицу по данной формуле до 9:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34\\ \hline \end{array}\]
По формуле \(R(10) = R(9) + R(8) = 55\), но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно \(R(10) = R(9) = 34\).
Заполним таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 34 & 68 & 102 & 170 & 272\\ \hline \end{array}\]
Отсюда получаем искомое количество программ — 272.
Ответ: 272