3. У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 1; 2. умножь на 2; 3. умножь на 3. Сколько есть программ, которые число 1 преобразуют в число 18?

Обозначим через \(N(n)\) число программ, переводящих 1 в число \(n\). Последняя команда могла быть «прибавь 1», «умножь на 2» или «умножь на 3», если соответствующая обратная операция даёт целое число. Поэтому \(N(n)=N(n-1)+N(n/2)+N(n/3)\), включая только целые аргументы, а для числа 1 полагаем \(N(1)=1\).

Последовательно получаем: \(N(2)=2\), \(N(3)=3\), \(N(4)=5\), \(N(5)=5\), \(N(6)=10\), \(N(7)=10\), \(N(8)=15\), \(N(9)=18\), \(N(10)=23\), \(N(11)=23\), \(N(12)=38\), \(N(13)=38\), \(N(14)=48\), \(N(15)=53\), \(N(16)=68\), \(N(17)=68\).

Для 18 последняя команда могла быть: «прибавь 1» от 17, «умножь на 2» от 9 или «умножь на 3» от 6. Значит, \(N(18)=N(17)+N(9)+N(6)=68+18+10=96\).

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