Question

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?

Answer 1

Заполняем таблицу:

Число -> Источники (из каких чисел можно получить текущее) -> Количество способов получения числа.

Число 3 можно получить только одним способом из числа 3 с помощью "пустой" программы.

Число 4 - из числа 3 (1 способ)

Число 5- из числа 4 (1 способ)

Число 6 - из числа 3 (1 способ) и из числа 5 (1 способ). Всего 1+1=2 способа

Число 7 - из числа 4 (1 способ) и из числа 6 (2 способа). Всего 1+2=3 способа

Некоторые варианты выбрасываем:

Число 11 - только из числа 8 (4 способов)

Число 13 - только из числа 12 (10 способов)

Выбрасываем также варианты, которые проходят "мимо" числа 15, например 12-13-16 или 13-14-17

Итого получаем 96 способов для числа 20 (см.таблицу)