Решение: Траектория вычислений с числом 10
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 2, умножить на 2 и прибавить 3. Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Решение по шагам
4 шагаВведём динамическое подсчитывание количества программ, ведущих из одного числа в другое. Для попадания в число $x$ последняя команда могла быть одной из трёх: прибавление 2, умножение на 2 или прибавление 3.
Отдельно подсчитываем программы перехода от исходного числа 2 к числу 10 и программы перехода от числа 10 к числу 21. По рекуррентному подсчёту получаем по 9 программ для каждого участка.
Так как все команды увеличивают число, после прохождения числа 10 вернуться к нему невозможно. Поэтому любую подходящую программу можно однозначно разделить в месте получения числа 10.
Общее число программ равно произведению количества вариантов для двух участков.
$$N=9\cdot9=81$$Где здесь ошибаются
Складывают, а не перемножают количество вариантов до числа 10 и после него.
Не учитывают команду «умножить на 2» при подсчёте переходов.
Считают программы, которые не содержат число 10 в траектории.