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

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

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

2.  Пусть n де­лит­ся на 3. Тогда R(n)  =  R(n : 3) + R(n – 2) (если n > 3).

При n  =  3 R(n)  =  2 (два спо­со­ба: при­бав­ле­ни­ем двой­ки или од­но­крат­ным умно­же­ни­ем на 3). По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех не­чет­ных чисел, крат­ных трем и не пре­вос­хо­дя­щих 31.

Имеем:

R(1)= 1;

R(3) = 2 = R(5)=R(7);

R(9) = R(3)+R(7) = 2+2 = 4 = R(11) = R(13);

R(15) = R(5)+R(13) = 2+4 = 6 = R(17) = R(19);

R(21) = R(7)+R(19) = 2+6 = 8 = R(23) = R(25);

R(27) = R(9)+R(25) = 4+8 =12 = R(29) = R(31).

Ответ: 12.

Дру­гой спо­соб ре­ше­ния.

Оче­вид­но, из числа 1 нель­зя по­лу­чить чет­ное число. Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 3, 5, …, 31 (то есть для каж­до­го из таких чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, обо­зна­чим R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, то есть даст число боль­ше 1. Зна­чит, R(1)  =  1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на три, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го не­чет­но­го числа с по­мо­щью ко­ман­ды при­бавь 2. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го не­чет­но­го числа: R(i)  =  R(i – 2). Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 2 и умножь на 3, тогда R(i)  =  R(i – 2) + R(i : 3). За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ве­ден­ным фор­му­лам слева на­пра­во:

При­ведём дру­гое ре­ше­ние на языке Python.

Для сло­же­ния спра­вед­лив пе­ре­ме­сти­тель­ный (ком­му­та­тив­ный) закон, зна­чит, по­ря­док ко­манд в про­грам­ме не имеет зна­че­ния для ре­зуль­та­та.

Обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число, по­это­му ко­ли­че­ство ко­манд не может пре­вос­хо­дить 15 − 2  =  13. При этом ми­ни­маль­ное ко­ли­че­ство ко­манд  — 5 (так как (15 − 2) : 3  =  4 с остат­ком 1). При этом за­ме­тим, что 15  — не­чет­ное, а 2  — чет­ное. А так как обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число на не­чет­ное число, то ко­ли­че­ство ко­манд долж­но быть не­чет­ным.

Иначе го­во­ря, ко­манд может быть 5, 7, 9, 11 или 13. По­сколь­ку, как было ска­за­но выше, по­ря­док ко­манд не имеет зна­че­ния, каж­до­му числу ко­манд со­от­вет­ству­ет один набор ко­манд, ко­то­рые можно рас­по­ло­жить в любом по­ряд­ке. Пяти ко­ман­дам со­от­вет­ству­ет набор 22221 (5 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 7 ко­ман­дам  — набор 2221111 (здесь по­лу­ча­ет­ся 35 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния: это число пе­ре­ста­но­вок с по­вто­ре­ни­я­ми P₇(3,4)=7! / (3! · 4!)), 9 ко­ман­дам  — 22111111 (здесь по­лу­ча­ет­ся 36 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 11 ко­ман­дам  — 21111111111 (11 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 13 ко­ман­дам  — 11111111111111 (1 ва­ри­ант рас­по­ло­же­ния). Всего имеем 88 про­грамм.

Ответ: 88.

При­ведём дру­гое ре­ше­ние на языке Python.

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

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

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

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

Тогда R(n)  =  R(n : 2) + R(n : 3) + R(n – 1).

До­ста­точ­но вы­чис­лить все зна­че­ния R(n).

Имеем:

R(2)  =  2 (можно умно­жить еди­ни­цу на 2 или при­ба­вить 1);

R(3)  =  3 (можно умно­жить еди­ни­цу на 3 или при­ба­вить 1 к двой­ке, ко­то­рую, в свою оче­редь, можно по­лу­чить двумя спо­со­ба­ми (см. выше);

R(4)  =  R(2) + R(3)  =  5;

R(5)  =  R(4)  =  5;

R(6)  =  R(2) + R(3) + R(5)  =  10;

R(7)  =  R(6)  =  10;

R(8)  =  R(4) + R(7)  =  5 + 10  =  15;

R(9)  =  R(3) + R(8)  =  3 + 15  =  18;

R(10)  =  R(5) + R(9)  =  5 + 18  =  23;

R(11)  =  R(10)  =  23;

R(12)  =  R(11) + R(4) + R(6)  =  23 + 5 + 10  =  38;

R(13)  =  R(12)  =  38.

Ответ: 38.

При­ведём дру­гое ре­ше­ние на языке Python.

Обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число. Стар­шая цифра  — 3. Сле­до­ва­тель­но, ис­поль­зо­вать ко­ман­ду 2 более двух раз бес­смыс­лен­но.

Вы­пи­шем про­грам­мы, в ко­то­рых ко­ман­да 2 ис­поль­зу­ет­ся два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 про­грамм.

Вы­пи­шем про­грам­мы, в ко­то­рых ко­ман­да 2 ис­поль­зу­ет­ся один раз. Ис­поль­зо­вав эту ко­ман­ду в пер­вой по­зи­ции, мы по­лу­чим из числа 35 число 45. Сле­до­ва­тель­но, после этого не­об­хо­ди­мо будет до­пи­сать ещё 12 ко­манд 1, чтобы по­лу­чить число 57. Таким об­ра­зом, по­лу­ча­ем про­грам­мы: 211...1, 121...1 и так далее. Итого имеем 13 про­грамм (двой­ка по­бы­ва­ла в каж­дой по­зи­ции).

Су­ще­ству­ет всего одна про­грам­ма, в ко­то­рой ко­ман­да 2 не ис­поль­зу­ет­ся: 111....1.

Таким об­ра­зом, имеем 6 + 13 + 1  =  20 про­грамм.

Ответ: 20.

При­ведём дру­гое ре­ше­ние на языке Python.

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

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

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)  =  2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и удво­е­ни­ем). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20.

Имеем:

R(3)  =  1;

R(4)  =  2  =  R(5);

R(6)  =  R(3) + R(4)  =  1 + 2  =  3  =  R(7);

R(8)  =  R(4) + R(6)  =  2 + 3  =  5  =  R(9);

R(10)  =  R(5) + R(8)  =  2 + 5  =  7  =  R(11);

R(12)  =  R(6) + R(10)  =  3 + 7  =  10  =  R(13);

R(14)  =  R(7) + R(12)  =  3 + 10  =  13  =  R(15);

R(16)  =  R(8) + R(14)  =  5 + 13  =  18  =  R(17);

R(18)  =  R(9) + R(16)  =  5 + 18  =  23  =  R(19);

R(20)  =  R(10) + R(18)  =  7 + 23  =  30  =  R(21);

R(22)  =  R(11) + R(20)  =  7 + 30  =  37.

Ответ: 37.

При­ведём дру­гое ре­ше­ние на языке Python.