Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 2; 2. Прибавить 3; 3. Прибавить 5. Сколько существует программ, для которых при исходном числе 5 результатом является число 25, и при этом траектория вычислений содержит либо 13, либо 17, но не 13 и 17 одновременно?

Ответ: 252 программы.

Решение

Исполнитель умеет выполнять три команды:

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

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

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

Нужно найти количество программ, которые преобразуют число 5 в число 25, причём траектория вычислений содержит либо 13, либо 17, но не оба числа одновременно.

Поскольку все команды увеличивают число, исполнитель не может вернуться к уже пройденному значению.

1. Введём функцию для подсчёта программ

Обозначим через $F(n)$ количество способов увеличить число на $n$, используя команды +2, +3 и +5.

Тогда:

Начальные условия:

Последовательно вычислим значения:

2. Найдём количество программ, проходящих через 13

Чтобы попасть из 5 в 13, нужно увеличить число на 8:

Чтобы попасть из 13 в 25, нужно увеличить число на 12:

По правилу умножения получаем:

Таким образом, через число 13 проходят 162 программы. Однако среди них есть программы, проходящие также через 17.

3. Найдём количество программ, проходящих через 17

Из 5 в 17:

Из 17 в 25:

Следовательно:

Через число 17 проходят 162 программы, включая программы, которые проходят и через 13.

4. Найдём количество программ, проходящих через оба числа

Так как команды только увеличивают число, программа, проходящая через 13 и 17, обязательно имеет вид:

Подсчитаем количество способов для каждого участка:

• От 5 до 13: $F(8)=6$.

• От 13 до 17: $F(4)=1$, поскольку возможны только две команды +2.

• От 17 до 25: $F(8)=6$.

Получаем:

5. Вычислим окончательный ответ

По условию программа должна проходить ровно через одно из двух чисел.

Если просто сложить количества программ, проходящих через 13 и через 17, то программы, проходящие через оба числа, будут учтены дважды.

Поэтому необходимо вычесть их количество два раза:

Подставим значения:

Ответ: 252.