Исполнитель САЛФЕТОЧКА преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя САЛФЕТОЧКА — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений не содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число \(n\). Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-2)\)
Заполним таблицу по данной формуле до 7:
\[\begin {array}{|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13\\ \hline \end{array}\] Так как по условию сказано, что траектория не должна проходить через число 8, значит мы никак не можем его получить, что означает \(R(8) = 0\).
Заполним таблицу до конца:
\[\begin {array}{|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 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 0 & 13 & 13 & 26 & 39 & 65 & 104 \\ \hline \end{array}\] Осюда получаем ответ — 104.
Ответ: 104