У исполнителя Арифметик две команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 3.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3.
Программа для Арифметика — это последовательность команд.
Сколько существует программ, которые число 7 преобразуют в число 20?
Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.
Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 20 − 7 = 13. При этом минимальное количество команд — 5 (так как (15 − 2)/3 = 4, 15−3 · 4 = 1 = 1 · 1). При этом заметим, что 7 — нечетное, а 20 — четное. А так как обе команды увеличивают исходное число на нечетное число, то количество команд должно быть нечетным.
Иначе говоря, команд может быть 5, 7, 9, 11 или 13. Так как, как было сказано выше, порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке. 5 командам соответствует набор 22221 (5 возможных вариантов расположения), 7 командам — набор 2221111 (35 возможных вариантов расположения: это число перестановок с повторениями P7(3,4) = 7!/(3! · 4!)), 9 командам — 22111111 (36 возможных вариантов расположения), 11 командам — 21111111111 (11 возможных вариантов расположения), 13 командам — 11111111111111 (1 вариант расположения). Всего получается 88 программ.
Ответ: 88.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
else:
return f(x + 1, y) + f(x + 3, y)
print(f(7, 20))

