1. Исполнитель преобразует число, записанное на экране. У исполнителя есть команды, которым присвоены номера: 1. Вычесть 2. 2. Вычесть 3. 3. Разделить нацело на 3. Первая команда уменьшает число на 2, вторая — на 3, третья уменьшает число в 3 раза. Сколько существует программ, для которых при исходном числе 20 результатом является число 3?

Чтобы подсчитать программы, рассмотрим обратные действия: прибавить 2, прибавить 3 или умножить на 3. Обозначим через f(n) число способов получить n из 3 обратными действиями.

Начальное значение: f(3)=1. Далее используем правило: f(n)=f(n−2)+f(n−3)+f(n/3), если n делится на 3; слагаемое f(n/3) учитывается только в этом случае.

Вычисляя значения до 20, получаем: f(18)=40, f(19)=45, f(20)=f(18)+f(17)=40+26=66.

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