Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он выполняет команды: A — вычесть 1, B — вычесть 4, C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 7 и содержит 13? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Шешім по шагам
5 қадамТак как все команды уменьшают число, траектория обязательно проходит через 13 ровно один раз. Поэтому количество подходящих программ равно произведению числа способов попасть из 19 в 13 и числа способов попасть из 13 в 2, избегая числа 7.
Обозначим через $f(n)$ число способов попасть из $n$ в 13. Для $n>13$ учитываем переходы $n\to n-1$, $n\to n-4$ и $n\to \lfloor n/3\rfloor$. Число 7 не может быть промежуточным состоянием.
$$f(13)=1,\quad f(14)=1,\quad f(15)=1,\quad f(16)=1,\quad f(17)=2,\quad f(18)=3,\quad f(19)=4$$Следовательно, из 19 в 13 можно попасть четырьмя способами.
Теперь обозначим через $g(n)$ число способов попасть из $n$ в 2, не проходя через 7. При $g(2)=1$, а для остальных допустимых состояний используем те же три перехода.
$$g(3)=1,\ g(4)=1,\ g(5)=1,\ g(6)=3,\ g(7)=0,\ g(8)=2,\ g(9)=4,\ g(10)=8,\ g(11)=9,\ g(12)=12,\ g(13)=17$$Из 13 в 2 существует 17 допустимых способов. Общее число программ равно:
$$4\cdot17=68$$Где здесь ошибаются
Не исключают траектории, проходящие через число 7.
Считают только число способов попасть из 19 в 2, не требуя прохождения через 13.
Забывают, что команда C задаёт переход к $\lfloor n/3\rfloor$.