Нужно сначала преобразовать 1 в 12, а затем 12 в 40, не заходя в 14.
Пусть F(b) – количество программ, преобразующих исходное число 1 в число b. Это число равно сумме F(x) для всех x, из которых можно одной командой получить b. Будем находить значения F(b) последовательно для всех b от 1 до 12:
F(1) = 1 (единственная программа, сохраняющая исходное число, – пустая)
F(2) = F(1) + F(1) = 2 (от 1 можно перейти к 2 двумя способами)
F(3) = F(2) + F(1) = 2 + 1 = 3
F(4) = F(3) + F(2) = 3 + 2 = 5
F(5) = F(4) = 5
F(6) = F(5) + F(3) + F(2) = 5 + 3 + 2 = 10
F(7) = F(6) = 10
F(8) = F(7) + F(4) = 10 + 5 = 15
F(9) = F(8) + F(3) = 15 + 3 = 18
F(10) = F(9) + F(5) = 18 + 5 = 23
F(11) = F(10) = 23
F(12) = F(11) + F(6) + F(4) = 23 + 10 + 5 = 38
Рассмотрим теперь переход от 12 к 40. Чтобы «обойти» число 14, нужно выполнить умножение. Можно умножить 12 на 2 или на 3, получится 24 или 36. В любом из этих случаев дальнейшее умножение невозможно – получится число больше 40, поэтому придётся прибавлять по 1 до 40. Можно увеличить 12 на 1, получится 13, после этого можно выполнить умножение на 2 или на 3 и далее прибавлять по 1 до 40. Всего получается 4 способа перехода от 12 к 40 без захода в 14.
Любой из способов перехода от 1 к 12 можно совместить с любым из способов перехода от 12 к 40, всего получается
38 · 4 = 152 программы.