Шешімі: Подсчёт программ Вычислителя
Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды: прибавить 1 и умножить на 2. Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для Вычислителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 22, траектория вычислений содержит число 10 и не содержит числа 15? Траектория вычислений программы — это последовательность результатов выполнения всех команд. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Шешім по шагам
5 қадамОбозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Последняя команда перед получением $n$ могла быть прибавлением 1 или умножением на 2.
$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$Последовательно получаем значения до числа 10:
$$f(1)=1,\ f(2)=2,\ f(3)=2,\ f(4)=4,\ f(5)=4,\ f(6)=6,\ f(7)=6,\ f(8)=10,\ f(9)=10,\ f(10)=14$$Так как все команды увеличивают число, после прохождения числа 10 траектория уже не может вернуться к нему. Посчитаем пути от 10 до 22. Всего их 3: два проходят через последовательный переход к 20 и один использует переход $11 \to 22$.
$$g(22)=g(21)+g(11)=2+1=3$$Один из трёх путей проходит через число 15, поэтому допустимых путей от 10 до 22 остаётся 2.
$$3-1=2$$Перемножаем количество нұсқа первой и второй частей программы.
$$14\cdot 2=28$$Где здесь ошибаются
Не учитывать, что для числа 2 существуют две разные последние команды: прибавить 1 и умножить на 2.
Не разделять траекторию на участок от 1 до 10 и участок от 10 до 22.
Не исключить путь, проходящий через число 15.