Исполнитель преобразует число, записанное на экране.

У исполнителя есть три команды, которым присвоены номера:

A. Прибавить 1

B. Прибавить 2

C. Умножить на 2

Программа для исполнителя — это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 3 в число 15 и при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна содержать оба указанных числа.

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Для решения задачи можно использовать метод перебора всех возможных программ, которые могут привести исходное число 3 к числу 15 и содержат числа 9 и 11 в траектории.

Обозначим команды A, B и C соответственно цифрами 1, 2 и 3. Тогда каждая программа будет представляться последовательностью цифр.

Начнем перебор с программ длины 3, так как чтобы пройти через числа 9 и 11, нужно выполнить как минимум 3 команды. Для каждой программы будем последовательно выполнять команды, начиная с числа 3, и проверять, приводит ли это к числу 15 и содержит ли траектория числа 9 и 11.

Перебор всех возможных программ длины 3 дает следующие результаты:

- 111 не подходит, так как не содержит чисел 9 и 11 в траектории.
- 112 не подходит, так как не содержит числа 11 в траектории.
- 113 не подходит, так как не содержит числа 9 в траектории.
- 121 не подходит, так как не содержит числа 11 в траектории.
- 122 не подходит, так как не содержит числа 9 в траектории.
- 123 не подходит, так как не приводит к числу 15.
- 131 не подходит, так как не содержит числа 11 в траектории.
- 132 не подходит, так как не содержит числа 9 в траектории.
- 133 не подходит, так как не приводит к числу 15.
- 211 не подходит, так как не содержит числа 9 в траектории.
- 212 не подходит, так как не содержит числа 11 в траектории.
- 213 не подходит, так как не приводит к числу 15.
- 221 не подходит, так как не содержит числа 9 в траектории.
- 222 не подходит, так как не приводит к числу 15.
- 223 не подходит, так как не содержит числа 11 в траектории.
- 231 не подходит, так как не приводит к числу 15.
- 232 не подходит, так как не содержит числа 11 в траектории.
- 233 не подходит, так как не содержит числа 9 в траектории.
- 311 не подходит, так как не содержит числа 11 в траектории.
- 312 не подходит, так как не содержит числа 9 в траектории.
- 313 не подходит, так как не приводит к числу 15.
- 321 не подходит, так как не содержит числа 11 в траектории.
- 322 не подходит, так как не приводит к числу 15.
- 323 не подходит, так как не содержит числа 9 в траектории.
- 331 не подходит, так как не приводит к числу 15.
- 332 не подходит, так как не содержит числа 9 в траектории.
- 333 не подходит, так как не содержит числа 11 в траектории.

Таким образом, существует только одна программа, которая приводит исходное число 3 к числу 15 и содержит числа 9 и 11 в траектории. Это программа 223.