Количество программ, проходящих через заданное число
Исполнитель РЫБИНСК преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя РЫБИНСК — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-2)\)
Заполним таблицу по данной формуле до 9:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34\\ \hline \end{array}\]
По формуле \(R(10) = R(9) + R(8) = 55\), но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно \(R(10) = R(9) = 34\).
Заполним таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 34 & 68 & 102 & 170 & 272\\ \hline \end{array}\]
Отсюда получаем искомое количество программ — 272.
Исполнитель Яблочко преобразует число, записанное на экране.
У исполнителя есть команды, которым присвоены номера:
1. Прибавить 2,
2. Прибавить 3,
3. Умножить на 3
Первая команда увеличивает число на экране на 2, вторая — на 3, третья — утраивает число на экране. Программа для исполнителя Яблочко — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 28 и при этом троектория содержит числа 12 и 18? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 9, 12, 14.
Пусть \(R(n)\) — количество программ, которык число 3 преобразуют в число n. Тогда верно следующее утверждение:
\(R(n) = R(n-2) + R(n-3)\) — если число не делится на 3.
\(R(n) = R(n-2) + R(n-3) + R(n:3)\) — если число делится на 3.
Заполним таблицу по данным формулам до 12:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6\\ \hline \end{array}\]
По условию дано, что траектория проходит через число 12. Значит \(R(13) = 0\). Продлим таблицу до 18:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6 & 0 & 6 & 6 & 6 & 12 & 12\\ \hline \end{array}\]
По условию сказано, что траектория должна проходить через числа 12 и 18. следовательно \(R(19) = 0\), так как число 19 нельзя получить напрямую из 12 или 18. Составим таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 \\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6 & 0 & 6 & 6 & 6 & 12 & 12 & 0 & 12 & 12 & 12 & 24 & 24 & 36 & 48 & 60 & 84 \\ \hline \end{array}\]
Отсюда получаем ответ — 84.
Исполнитель Калькулятор преобразует число, записанное на экране.
У исполнителя есть команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 5,
3. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая — на 5, третья — удваивает число на экране. Программа для исполнителя Калькулятор — это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 24 и при этом троектория содержит числа 11 и 17 ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 13, 14.
Пусть \(R(n)\) — количество программ, которые число 4 преобразуют в число \(n\). Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-5)\) — если число не делится на 2.
\(R(n) = R(n-1) + R(n-5) + R(n:2)\) — если число делится на 2.
Заполним таблицу по данным формулам до 11:
\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6\\ \hline \end{array}\]
По условию траектория должна проходить через число 11, значит \(R(12) = 6\), так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6 & 6 & 6 & 6 & 6 & 12 & 18 & 24\\ \hline \end{array}\]
Аналагично \(R(19) = 24\), так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6 & 6 & 6 & 6 & 6 & 12 & 18 & 24 & 24 & 24 & 24 & 24 & 48 & 72\\ \hline \end{array}\]
Отсюда получаем ответ: 72.
Исполнитель Школково преобразует число, записанное на экране.
У исполнителя есть команды, которым присвоены номера:
1. Прибавить 2,
2. Прибавить 3,
3. Умножить на 2,
4. Умножить на 3.
Первая команда увеличивает число на экране на 2, вторая – на 3, третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя Школково — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 38 и при этом троектория содержит числа 14 и 29? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Пусть \(R(n)\) — количество программ, которые число 2 преобразует в число \(n\). Тогда верно следующее утверждение:
\(R(n) = R(n-2) + R(n-3)\) — если число не делится на 2 и на 3.
\(R(n) = R(n-2) + R(n-3) + R(n:2)\) — если число делится на 2, но не делится на 3.
\(R(n) = R(n-2) + R(n-3) + R(n:3)\) — если число делится на 3, но не делится на 2.
\(R(n) = R(n-2) + R(n-3) + R(n:2) + R(n:3)\) – если число делится и на 2, и на 3.
Заполним таблицу по данным формулам до 14:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 0 & 2 & 1 & 3 & 3 & 6 & 6 & 10 & 12 & 21 & 22 & 36\\ \hline \end{array}\]
По условию траектория должна проходить через число 14, значит \(R(15) = 0\), так как мы никак не можем получить число 15, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29\\ \hline 36 & 0 & 36 & 36 & 36 & 72 & 72 & 108 & 144 & 180 & 252 & 324 & 432 & 576 & 756 & 1008\\ \hline \end{array}\]
Аналогично \(R(30) = 0\), так как число 30 никак нельзя получить, чтобы траектория проходила через число 29. Заполним таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38\\ \hline 1008 & 0 & 1008 & 1008 & 1008 & 2016 & 2016 & 3024 & 4032 & 5040\\ \hline \end{array}\]
Отсюда получаем ответ: 5040.
Исполнитель Ребус преобразует число, записанное на экране.
У исполнителя есть команды, которым присвоены номера:
1. Прибавить 1,
2. Прибавить 2,
3. Умножить на 2,
4. Умножить на 3.
Первая команда увеличивает число на экране на 1, вторая — на 2, третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя Ребус — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 27 и при этом троектория содержит числа 13 и 19 ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Пусть \(R(n)\) — количество программ, которые число 2 преобразуют в число \(n\). Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-2)\) — если число не делится на 2 и на 3.
\(R(n) = R(n-1) + R(n-2) + R(n:2)\) — если число делится на 2, но не делится на 3.
\(R(n) = R(n-1) + R(n-2) + R(n:3)\) — если число делится на 3, но не делится на 2.
\(R(n) = R(n-1) + R(n-2) + R(n:2) + R(n:2)\) — если число делится и на 2, и на 3.
Используя данные формулы, заполним таблицу до 13:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline 1 & 1 & 3 & 4 & 9 & 13 & 25 & 39 & 68 & 107 & 187 & 294\\ \hline \end{array}\]
По условию траектория должна проходить через число 13, значит \(R(14) = 294\), так как число 14 мы можем полчить только командой 1 из числа 13, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:
\[\begin{array}{|c|c|c|c|c|c|c|} \hline 13 & 14 & 15 & 16 & 17 & 18 & 19\\ \hline 294 & 294 & 588 & 882 & 1470 & 2352 & 3822\\ \hline \end{array}\]
Аналогично \(R(20) = 3822\). Заполним таблицу до конца:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27\\ \hline 3822 & 3822 & 7644 & 11466 & 19110 & 30576 & 49686 & 80262 & 129948\\ \hline \end{array}\]
Отсюда получаем ответ – 129948.
Исполнитель ПЕЧЕНЬКА преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1,
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая — удваивает его. Программа для исполнителя ПЕЧЕНЬКА — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 17 и при этом троектория содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Пусть \(R(n)\) — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:
\(R(n) = R(n-1)\) — если число n не делится на 2.
\(R(n) = R(n-1) + R(n:2)\)
Заполним таблицу по данной формуле до 10:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text{1}& 1 & 2 & 2 & 3 & 3 & 5 & 5 & 7 \\ \hline \end{array}\] Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — \(R(12) = R(11)\). Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.
В итоге получаем ответ — 7
Исполнитель Студент преобразует число, записанное на экране.
У исполнителя есть команды, которым присовены номера:
1. Прибавить 1,
2. Прибавить 3,
3. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая — на 3, третья — удваивает число на экране. Программа для исполнителя Студент — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 17 и при этом троектория содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 11, 22.
Пусть \(R(n)\) — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:
\(R(n) = R(n-1) + R(n-2)\) — если число не делится на 2.
\(R(n) = R(n-1) + R(n-2) + R(n:2)\) — если число делится на 2.
Заполним таблицу по данным формулам до 10:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text {1}& 1 & 2 & 3 & 5 & 7 & 12 & 17 & 27 \\ \hline \end{array}\]
По условию сказано, что траектория должна проходить через число 10, значит \(R(11) = 30\), так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:
\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \text {1}& 1 & 2 & 3 & 5 & 7 & 12 & 17 & 27 & 27 & 27 & 54 & 81 & 108 & 162 & 243\\ \hline \end{array}\]
Отсюда получаем ответ — 243.