Решение: Подсчёт программ исполнителя К17
Исполнитель К17 преобразует число, записанное на экране. Он выполняет три команды: прибавить 1, прибавить 2 и умножить на 2. Программа для исполнителя К17 — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 14 и при этом траектория вычислений содержит числа 10 и 12? Траектория должна содержать оба указанных числа. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговТак как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в указанном порядке. Поэтому искомое количество программ является произведением числа способов пройти три участка.
$$N(4,14;10,12)=N(4,10)\cdot N(10,12)\cdot N(12,14)$$Посчитаем количество способов попасть из 4 в 10. Для каждого числа учитываются переходы из чисел на 1 и 2 меньше, а также из числа вдвое меньшего, если оно целое.
$$N(4,10)=16$$Из 10 в 12 можно попасть двумя способами: дважды прибавить 1 или один раз прибавить 2.
$$N(10,12)=2$$Из 12 в 14 также существует два способа: дважды прибавить 1 или один раз прибавить 2.
$$N(12,14)=2$$Перемножаем количества способов для трёх независимых участков.
$$16\cdot 2\cdot 2=64$$Где здесь ошибаются
Не учитывать команду «умножить на 2» при подсчёте маршрутов.
Складывать, а не перемножать количества способов для участков.
Считать программы, в траектории которых есть только одно из чисел 10 и 12.