Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 2; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 20 результатом является число 3, при этом траектория вычислений не содержит чисел 13 и 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 4, 2, 1.
Шешім по шагам
4 қадамПусть $f(n)$ — число программ, переводящих число $n$ в число 3 и не содержащих в траектории чисел 13 и 14. Для числа 3 учитываем пустую последовательность команд: $f(3)=1$.
$$f(3)=1$$Последняя команда программы может быть A, B или C. Поэтому для остальных разрешённых значений $n$ количество программ равно сумме количества программ для чисел $n-1$, $n-2$ и $\lfloor n/3\rfloor$.
$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$Так как траектория не должна содержать числа 13 и 14, устанавливаем $f(13)=f(14)=0$. Последовательное вычисление даёт:
$$f(15)=2,\ f(16)=4,\ f(17)=8,\ f(18)=15,\ f(19)=26$$Для исходного числа 20 получаем:
$$f(20)=f(19)+f(18)+f(6)=26+15+3=44$$Где здесь ошибаются
Не исключают программы, в траектории которых встречается 13 или 14.
Ошибочно считают число 3 запрещённым начальным состоянием вместо конечного результата.
Забывают, что команда C переводит число $n$ в $\lfloor n/3\rfloor$.