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

Обозначим через \(f(n)\) число программ, переводящих 2 в \(n\). Последняя команда может быть либо «прибавить 1», либо «умножить на 3», поэтому:

\(f(n)=f(n-1)+f(n/3)\), если \(n\) делится на 3; иначе \(f(n)=f(n-1)\).

Последовательное вычисление даёт \(f(70)=95\).

Число программ, проходящих через 22, равно произведению числа путей от 2 до 22 и числа путей от 22 до 70:

\(f(22)=9\), а число путей от 22 до 70 равно 3. Поэтому через 22 проходят \(9\cdot3=27\) программ.

Искомое число программ: \(95-27=68\).

Ответ: 68