Решение: Программы с числом 12
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: умножить число на 3, прибавить 2, прибавить 3. Программа для Вычислителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговПоскольку все команды увеличивают число, число 12 в траектории может встретиться только один раз. Поэтому число искомых программ равно произведению числа программ из 2 в 12 и числа программ из 12 в 21.
$$N = N_{2\to12} \cdot N_{12\to21}$$Для подсчёта используем динамическое программирование. Для каждой точки складываем количества способов попасть в неё командами «прибавить 2», «прибавить 3» и «умножить на 3», если соответствующий переход возможен.
$$f(x)=f(x-2)+f(x-3)+\begin{cases}f(x/3),&x\mathrel{\vdots}3\\0,&\text{иначе}\end{cases}$$Количество программ из 2 в 12 равно 10.
$$N_{2\to12}=10$$Количество программ из 12 в 21 равно 5.
$$N_{12\to21}=5$$Перемножаем количества вариантов двух независимых частей программы.
$$N=10\cdot5=50$$Где здесь ошибаются
Складывают количество программ вместо умножения.
Не учитывают переходы командой «умножить на 3».
Считают программы, которые не проходят через число 12.