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

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

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

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

Тогда R(n) = R(n / 5) + R(n - 2)= R(n / 5) + R(n - 10) (если n > 10).

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

Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных десяти и не превосходящих 50: сначала вычисляем R(2), затем R(10), R(20) и т. д.

Имеем:

R(2) = 1 = R(4) = R(6) = R(8),

R(10) = 2 = R(2) + R(8),

R(20) = R(4) + R(10) =1 + 2 = 3 = R(22) = R(28),

R(30) = R(6) + R(20) =1 + 3 = 4 = R(32) = R(38),

R(40) = R(8) + R(30) =1 + 4 = 5 = R(42) = R(48),

R(50) = R(10) + R(40) = 2 + 5 = 7.

Ответ: 7.

Другая форма решения.

Будем решать поставленную задачу последовательно для чисел 2, 4, 6, 50 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Заметим, что нечётные числа мы никак получить не можем. Количество программ, которые преобразуют число 2 в число n, будем обозначать через R(n). Число 2 у нас уже есть, значит, его можно получить с помощью «пустой» программы. Любая непустая программа увеличит исходное число, т. е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на пять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа:

Если число на пять делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда . Заполним соответствующую таблицу по приведённым формулам слева направо:

При этом ячейки, относящиеся к числам, которые не делятся на 5, можно в решении и опустить (за исключением первого числа):

Ответ: 7.

Приведём решение Б. С. Михлина на языке Python.

Очевидно, из числа 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.