*Сле­ду­ю­щее рас­суж­де­ние удоб­но за­пи­сы­вать в виде де­ре­ва.

С по­мо­щью одной ко­ман­ды из числа 2 можно по­лу­чить 2 раз­лич­ных числа:

2 + 2 = 4,

2 * 3 = 6.

С по­мо­щью двух ко­манд можно по­лу­чить по два числа из 4 и 6:

4 + 2 = 6,

4 * 3 = 12,

6 + 2 = 8,

6 * 3 = 18.

С по­мо­щью трёх ко­манд по­лу­ча­ют­ся сле­ду­ю­щие числа.

12 + 2 = 14,

12 * 3 = 36,

8 + 2 = 10,

8 * 3 = 24,

18 + 2 = 20,

18 * 3 = 54,

Число 6 даст числа 8 и 18.

Итого: 8 чисел.

Ответ: 8.

Про­грам­ма может со­сто­ять из 0, 1, 2, 3 или 4 ко­манд; про­ана­ли­зи­ру­ем эти слу­чаи. Сле­ду­ю­щие рас­суж­де­ния удоб­но за­пи­сы­вать в виде де­ре­ва.

Не со­дер­жит ни одной ко­ман­ды одна про­грам­ма: она не из­ме­нит числа на экра­не, дав на вы­хо­де число 2.

С по­мо­щью одной ко­ман­ды из числа 2 можно по­лу­чить 2 раз­лич­ных числа:

2 + 2 = 4

2 * 3 = 6.

С по­мо­щью двух ко­манд можно по­лу­чить по два числа из 4 и 6:

4 + 2 = 6 .

4 * 3 = 12

6 + 2 = 8

6 * 3 = 18

Число 6 уже есть, по­это­му и все числа, ко­то­рые могут из него по­лу­чить­ся нам не ин­те­рес­ны, т. к. они все будут по­вто­рять уже име­ю­щи­е­ся. Т. е. мы по­лу­чи­ли 3 числа.

С по­мо­щью трёх ко­манд по­лу­ча­ют­ся сле­ду­ю­щие числа:

12 + 2 = 14

12 * 3 = 36

8 + 2 = 10

8 * 3 = 24

18 + 2 = 20

18 * 3 = 54

С по­мо­щью четырёх ко­манд из 6 чисел пред­став­лен­ных выше, можно по­лу­чить ещё 12 чисел. Но за­ме­тим, что 10 + 2 = 12, а это число у нас уже име­ет­ся, зна­чит, оста­лось 11 чисел.

Всего раз­лич­ных чисел: 1 + 2 + 3 + 6 + 11 = 23.

Ответ: 23.

*Сле­ду­ю­щее рас­суж­де­ние удоб­но за­пи­сы­вать в виде де­ре­ва.

С по­мо­щью одной ко­ман­ды из числа 2 можно по­лу­чить два раз­лич­ных числа:

2 + 1 = 3,

2 * 2 = 4.

С по­мо­щью двух ко­манд можно по­лу­чить че­ты­ре числа:

3 + 1 = 4,

3 * 2 = 6,

4 + 1 = 5,

4 * 2 = 8.

С по­мо­щью трёх ко­манд по­лу­ча­ют­ся сле­ду­ю­щие во­семь раз­лич­ных чисел:

4 + 1 = 5,

4 * 2 = 8,

5 + 1 = 6,

5 * 2 = 10,

8 + 1 = 9,

8 * 2 = 16,

6 + 1 = 7,

6 * 2 = 12.

С по­мо­щью четырёх ко­манд из 8 чисел, по­лу­чив­ших­ся выше, по­лу­чит­ся 16 чисел. Но за­ме­тим, что

5 * 2 = 10 и 9 + 1 = 10, по­это­му раз­лич­ных из них будет 15 чисел.

Ответ: 15.

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1.  Если n не де­лит­ся на 2, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n)  — при­бав­ле­ни­ем еди­ниц.

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 2 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 16.

Имеем:

R(2)= 2 = R(3),

R(4)= 2 + 2 = 4 = R(5),

R(6) = 2 + 4 = 6 = R(7),

R(8) = R(4)+R(6) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(8) = 4 + 10 = 14 = R(11),

R(12) = R(6) + R(10) = 6 + 14 = 20 = R(13),

R(14) = R(7) + R(12) = 6 + 20 = 26 = R(15),

R(16) = R(8) + R(14) = 10 + 26 = 36

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее число, крат­ное че­ты­рем, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 55.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1.  Если n не де­лит­ся на 4, то тогда R (n) = R(T(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из T(n) - при­бав­ле­ни­ем еди­ниц.

2.  Пусть n де­лит­ся на 4.

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 вы­пол­не­но: R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем трех еди­ниц или од­но­крат­ным умно­же­ни­ем на 4).

По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных че­ты­рем и не пре­вос­хо­дя­щих 55.

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29) = R(30) = R(31)

R(32) = R(8) + R(31) = 3 + 12 = 15 = R(33) = R(34) = R(35)

R(36) = R(9) + R(35) = 3 + 15 = 18 = R(37) = R(38) = R(39)

R(40) = R(10) + R(39) = 3 + 18 = 21 = R(41) = R(42) = R(43)

R(44) = R(11) + R(43) = 3 + 21 = 24 = R(45) = R(46) = R(47)

R(48) = R(12) + R(47) = 4 + 24 = 28 = R(49) = R(50) = R(51)

R(52) = R(13) + R(51) = 4 + 28 = 32 = R(53) = R(54) = R(55)

Ответ: 32.