Исполнитель Осень 16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера. 1. Прибавить 1. 2. Прибавить 2. 3. Прибавить 4. Первая команда…
Исполнитель Осень 16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера. 1. Прибавить 1. 2. Прибавить 2. 3. Прибавить 4. Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья увели чивает на 4. Программа для исполнителя Осень 16 это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 87 Траектория вычислений программы это последовательность результатов выполнения всех ко нанд програнны. Например, для програмны 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Давайте поэтапно разобремся с задачей.
Задача:
- Изначально число равно 1.
- Есть последовательность команд (программа), каждая команда — прибавление 1, 2, или 4.
- После выполнения всей программы получаем число 15.
- В траектории (последовательность промежуточных результатов) обязательно должно фигурировать число 87.
Нужно определить, сколько таких программ существует.
Шаг 1. Обозначения и идея
Обозначим:
- \( P \) — программа, последовательность команд \( c_1, c_2, \dots, c_k \).
- \( S_i \) — результат после \( i \)-й команды, исходя из начального числа 1.
Тогда:
\[ S_0 = 1 \] \[ S_{i} = S_{i-1} + c_i \]
где \( c_i \in \{1, 2, 4\} \).
Итак:
- В конце программы: \( S_k = 15 \).
- В траектории обязательно есть число 87, то есть существует индекс \( j \) такой, что \( S_j = 87 \).
Шаг 2. Каким образом можно достигнуть 87?
Поскольку всего программа заканчивается числом 15, а начиная со 1, то сумма всех прибавлений:
\[ \sum_{i=1}^k c_i = 15 - 1 = 14 \].
Обозначим:
- Общее количество команд \( k \),
- Общая сумма прибавлений (это сумма всех команд) — 14.
Поскольку команда может прибавлять либо 1, 2, или 4, сумма 14 — это сумма выборов из этих чисел.
Шаг 3. Иногда достигается 87
Пусть где-то на этапе программа достигает числа 87. Тогда:
\[ S_j = 87 \].
Обозначим:
- \( j \) — индекс шага, на котором достигается 87,
- После этого программы продолжаются, и всё ещё сумма прибавлений должна в итоге равняться 14.
Но есть важный момент: поскольку числа прибавлений — только 1, 2, 4, и начальное число 1, то, чтобы достигнуть 87, требуется определённое количество прибавлений.
Шаг 4. Максимально возможное число после \( j \)-го шага
Рассмотрим, как можно достичь числа 87 за некоторый шаг.
Обозначим:
- \( s_j = S_j \),
- на каждом шаге прибавляем 1, 2 или 4.
Чтобы добиться \( S_j = 87 \), начиная с 1, сумма прибавлений за \( j \) шагов должна равняться:
\[ S_j - 1 = \sum_{i=1}^j c_i = 87 - 1 = 86 \].
Это сумма всех прибавлений, то есть:
\[ \sum_{i=1}^j c_i = 86 \].
За \( j \) шагов сумму прибавлений равна 86, при этом каждый прибавляемый член \( c_i \in \{1, 2, 4\} \).
Шаг 5. Найти минимальное число шагов для достижения суммы 86
Чтобы понять возможные \( j \), найдём минимальное и максимальное число шагов:
- Минимальное при \( j \):
минимальная суммаза \( j \) шагов — это все прибавления по 1. Тогда:
\[ j_{\text{min}} = 86 \].
- Максимальное при \( j \):
максимальная сумма— все прибавления по 4:
\[ j_{\text{max}} = \lfloor 86/4 \rfloor + \text{остаток} \].
Т.к. сумма 86 — делится на 2, переберём:
\[ \text{Максимальное } j = \text{число прибавлений 4} + \text{число прибавлений 2 или 1} \leq 86/4 = 21.5, \] но так как нужно целые шаги, то:
- число прибавлений 4 — максимум 21 (чтобы не превысить сумму 86).
Посчитаем, сколько получится шагов при этом:
- Если выбраны 21 прибавлений по 4: сумма \( 21 \times 4 = 84 \).
- Тогда оставшаяся сумма \( 86 - 84 = 2 \), которая может быть достигнута одним прибавлением 2.
Общая сумма:
\[ 21 \text{ прибавлений по 4} + 1 \text{ прибавление 2} = 22 \text{ шагов} \].
Итого минимальное:
\[ j_{\text{min}} = 86 \text{ (при всех прибавлениях 1)}. \] Максимальное:
\[ j_{\text{max}} = 22. \]
Ответ: для достижения суммы 86, количество шагов \( j \) должны принадлежать диапазону:
\[ \boxed{ 86 \leq j \leq 22 } \]
Это невозможно, поскольку 86 > 22. Означает, что достичь суммы 86 за \( j \) шагов возможно только для \( j \geq 86 \). Но у нас есть ограничение: программа завершится на числе 15, сумма всех прибавлений — 14, а чтобы на шаге \( j \) было число 87, сумма всех прибавлений от начальной 1 должна быть 86, а значит, сумма всех прибавлений за всю программу — 14, что невозможно, ведь \( 86 > 14 \).
Заключение:
- Для достижения 87 за \( j \) шагов нужны прибавления сумма которых равна 86.
- Общая сумма всех прибавлений — 14.
- Невозможно получить сумму прибавлений 86 при сумме 14.
Следовательно, программа, которая достигает числа 87 на каком-либо этапе, не может иметь итоговую сумму прибавлений равную 14.
Итог:
Ответ: количеству программ, которые при исходном числе 1 в конце имеют число 15 и содержат число 87 в пути — нет таких программ.
Возможный ответ:
\[ \boxed{0} \]
Если есть дополнительные условия или если что-то нужно уточнить — сообщите!
