Правильный ответ:
Обозначим R(n) – количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное трем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 28.
Верны следующие соотношения:
1. Если n не делится на 3, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) – прибавлением единиц.
2. Пусть n делится на 3. Тогда R(n) = R(n/3)+R(n-1)= R(n/3)+R(n-3) (если n>3). При n=3 R(n) = 2 (два способа: прибавлением двух единиц или однократным умножением на 3).
Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных трем и не превосходящих 29: сначала вычисляем R(1), затем R(3), R(6) и т.д.
Имеем:
R(2)=1
R(3) = 2 = R(4)=R(5)
R(6) = R(2)+R(3) =1+2 = 3 = R(7)=R(8)
R(9) = R(3)+R(6) =2+3 =5 = R(10)=R(11)
R(12) = R(4)+R(9) = 2+5 = 7 = R(13)=R(14)
R(15) = R(5)+R(12) =2+7 =9 = R(16)=R(17)
R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20)
R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23)
R(24) = R(8)+R(21) = 3+ 15 = 18 = R(25)=R(26)
R(27) = R(9)+R(24) = 5 + 18 = 23 = R(28)=R(29)
Ответ: 23