Исполнитель Школково преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя Школково — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 19 и при этом траектория вычислений содержит число 8 и не содержит число 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 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(9) = 21\), так как число 9 можем получить только первой командой.
Продолжим заполнять таблицу:
\[\begin {array}{|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 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 21 & 42 & 63 & 105 & 168\\ \hline \end{array}\] В условии сказано, что траектория не содержит число 14. Значит \(R(14) = 0\).
Заполним таблицу до конца:
\[\begin {array}{|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 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 21 & 42 & 63 & 105 & 168 & 0 & 168 & 168 & 336 & 504 & 840\\ \hline \end{array}\] Отсюда получаем ответ — 840.
Ответ: 840