У исполнителя Тритон две команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 3.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3. Программа для Тритона — это последовательность команд. Сколько существует программ, которые число 22 преобразуют в число 35?
Для сложения справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.
Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 35 — 22 = 13. При этом минимальное количество команд — 5 (т. к. [35 − 22]/3 = 4). Заметим, что 35 — нечетное, а 22 — четное. Поскольку обе команды увеличивают исходное число на нечетное число, то количество команд должно быть нечетным.
Иначе говоря, команд может быть 5, 7, 9, 11 или 13. Пяти командам соответствует набор 22221 (5 возможных вариантов расположения), семи командам — набор 2221111 (35 возможных вариантов расположения: это число перестановок с повторениями P7(3,4) = 7!/(3! · 4!)), девяти командам — 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(22, 35))