Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он умеет выполнять команды: прибавить 1, умножить на 2 и умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд. Например, для программы $ABC$ при исходном числе 7 траектория состоит из чисел 8, 16, 48.
Решение по шагам
4 шагаПусть $f(n)$ — количество программ, переводящих число 2 в число $n$ без появления числа 14 в траектории. Начальное значение: $f(2)=1$, а для запрещённого числа полагаем $f(14)=0$.
Чтобы получить число $n$, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения $f(n-1)$, $f(n/2)$ и $f(n/3)$ только при целочисленном делении.
Последовательное вычисление даёт: $f(12)=15$, $f(13)=15$, $f(14)=0$, $f(15)=2$, $f(18)=19$, $f(21)=32$, $f(24)=62$, $f(27)=84$, $f(30)=95$, $f(33)=112$, $f(36)=154$, $f(39)=188$.
Следовательно, количество подходящих программ равно $f(39)=188$.
Где здесь ошибаются
Не исключают программы, в траектории которых встречается число 14.
Учитывают переходы делением на 2 или 3, даже если результат не является целым числом.
Считают только различные траектории, а не программы; разные последовательности команд должны учитываться отдельно.