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

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

Последовательно получаем: \(f(2)=2\), \(f(3)=2\), \(f(4)=4\), \(f(5)=4\), \(f(6)=6\), \(f(7)=6\), \(f(8)=10\), \(f(9)=10\), \(f(10)=14\), \(f(11)=14\), \(f(12)=20\), \(f(13)=20\), \(f(14)=26\), \(f(15)=26\), \(f(16)=36\).

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