С3 - 2012 ДЕМО

У исполнителя Утроитель две команды, которым присвоены номера:

1. прибавь 1,

2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая – утраивает его.

Программа для Утроителя – это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 29?

Ответ обоснуйте.

Содержание верного ответа и указания к оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)

Обозначим 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

Или вот так