Question

ДАЮ 50 БАЛЛОВ СРОЧНО!!!!!!!!!!!!!!!! ПОДРОБНО
У некоторого исполнителя «Двоечник» в системе команд всего две команды с номерами:
1 Умножить на 2
2 Прибавить 1
Первая из них удваивает, а вторая увеличивает исходное число на 1
Программа для исполнителя — это последовательность команд (например, 1212 из числа 1 сделает число
6).
Вопрос: Сколько существует РАЗЛИЧНЫХ программ, которые из числа 2 сделают число 22 ?

Answer 1

Почитал с помощью дерева

2-3-4-5-6-7-8-9-10-11-12-...-22 - цепь из 2; после числа 11 нет смысла умножать на 2 (+1)

С 6 до 11 мы можем умножить только 1 раз число на 2 и далее прибавлять 1 (+6)

При умножении 5 на 2 мы получаем 10. От данного числа у нас 3 способа дойти до 22 (10-20-21-22; 10-11-22; 10-11-12-...-22) (+3)

Из числа 4 мы получаем 8. У нас +5 вариантов получения 22 (+5)

Из числа 3 мы получаем 6 и имеем еще 7 вариантов (+7)

Теперь рассмотрим цепь

2-4-8-16-17-...-22.

из 4 мы имеем еще 10 вариантов (+10)

Из 8 имеем еще 5 вариантов (+5)

Ответ: 37