2. Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1. 2. Прибавить 2. 3. Умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 19 и при этом траектория вычислений содержит число 15 и не содержит число 6?

Все команды увеличивают число, поэтому числа в траектории строго возрастают. Посчитаем количество способов дойти от 4 до 15, не попадая в 6. Число способов попасть в каждое число равно сумме способов попасть в него командами «+1», «+2» и «×2».

Для чисел до 15, исключая 6, получаем: для 4 — 1 способ, 5 — 1, 7 — 1, 8 — 1, 9 — 2, 10 — 3, 11 — 5, 12 — 8, 13 — 13, 14 — 21, 15 — 34. Значит, до 15 можно дойти 34 способами, не проходя через 6.

От 15 до 19 число способов равно 5: из 15 можно попасть в 16, затем в 17, 18 и 19, считая все допустимые сочетания команд «+1» и «+2» (команда «×2» здесь не даёт промежуточного числа меньше 19).

Эти участки траектории можно соединить независимо, поэтому получаем 34·5=170.

Ответ: 170 программ.