Количество программ, не проходящих через заданное число

Задание 1 #13345

Исполнитель Семенова преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 1,

2. умножить на 2,

3. умножить на 3.

Первая команда увеличивает число на экране на 1, вторая — удваивает число, третья — утраивает число. Программа для исполнителя Семенова — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 38 и при этом траектория вычислений не содержит числа 9 , 24 и 32? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Показать решение

Пусть \(R(n)\) — количество программ, которое число 1 преобразует в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1)\) — если число не делится ни на 2, ни на 3.

\(R(n) = R(n-1) + R(n:2)\) — если число делится на 2, но не делится на 3.

\(R(n) = R(n-1) + R(n:3)\) — если число делится на 3, но не делится на 2.

\(R(n) = R(n-1) + R(n:2) + R(n:3)\) — если число делится на 2 и на 3.

Заполним таблицу по данным формулам до 8:

\[\begin {array}{|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \text{1}& 2 & 3 & 5 & 5 & 10 & 10 & 15 \\ \hline \end{array}\] Так как по условию сказано, что траектория не должна содержать число 9, значит \(R(9) = 0\). Продолжим заполнять таблицу:

\[\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|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ \hline \text{1}& 2 & 3 & 5 & 5 & 10 & 10 & 15 & 0 & 5 & 5 & 20 & 20 & 30 & 35 & 50 & 50 & 60 & 60 & 70 & 80 & 85 & 85\\ \hline \end{array}\] Аналогично \(R(24) = 0\). Продолжим заполнять таблицу:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{23}& 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31\\ \hline \text{85}& 0 & 0 & 20 & 20 & 50 & 50 & 90 & 90 \\ \hline \end{array}\] Аналогично \(R(32) = 0\). Заполним таблицу до конца:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{31}& 32 & 33 & 34 & 35 & 36 & 37 & 38\\ \hline \text{90}& 0 & 5 & 55 & 55 & 135 & 135 & 195\\ \hline \end{array}\] Отсюда получем ответ — 195

Ответ: 195

Задание 2 #12789

Исполнитель САЛФЕТОЧКА преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1,

2. Прибавить 2.

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя САЛФЕТОЧКА — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений не содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.

Показать решение

Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-2)\)

Заполним таблицу по данной формуле до 7:

\[\begin {array}{|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13\\ \hline \end{array}\] Так как по условию сказано, что траектория не должна проходить через число 8, значит мы никак не можем его получить, что означает \(R(8) = 0\).

Заполним таблицу до конца:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 0 & 13 & 13 & 26 & 39 & 65 & 104 \\ \hline \end{array}\] Осюда получаем ответ — 104.

Ответ: 104

Задание 3 #12790

Исполнитель Программист преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1,

2. Умножить на 2.

Первая команда увеличивает число на экране на 1, вторая увеличивает его в 2 раза. Программа для исполнителя Программист — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 19 и при этом траектория вычислений не содержит число 14? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.

Показать решение

Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n:2)\)

Заполним таблицу по данной формуле до 13:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline \text{1}& 2 & 2 & 4 & 4 & 6 & 6 & 10 & 10 & 14 & 14 & 20 & 20 \\ \hline \end{array}\] Так как по условию сказано, что траектория не должна проходить через число 14, значит мы никак не можем его получить, что означает \(R(14) = 0\).

Заполним таблицу до конца:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ \hline \text{1}& 2 & 2 & 4 & 4 & 6 & 6 & 10 & 10 & 14 & 14 & 20 & 20 & 0 & 0 & 10 & 10 & 20 & 20 \\ \hline \end{array}\] Отсюда получаем ответ — 20.

Ответ: 20

Задание 4 #12791

Исполнитель ЭВМ преобразует число, записанное на экране.

У исполнителя есть команды , которым присвоены номера:

1. Прибавить 1,

2. Прибавить 3,

3. Умножить на 2.

Первая команда увеличивает число на экране на 1, вторая — на 3, третья — удваивает число на экране. Программа для исполнителя ЭВМ — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 27 и при этом траектория вычислений не содержит числа 16 и 23? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Показать решение

Пусть \(R(n)\) — количество программ, которые число 1 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-3)\) — если число не делится на 2.

\(R(n) = R(n-1) + R(n-3) + R(n:2)\) — если число делится на 2.

Заполним таблицу по данной формуле до 15:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline \text{1}& 2 & 2 & 5 & 7 & 11 & 16 & 28 & 39 & 62 & 90 & 140 & 202 & 308 & 448 \\ \hline \end{array}\] Так как по условию сказано, что траектория не должна проходить через число 16, значит мы никак не можем его получить, что означает \(R(16) = 0\).

Продолжим заполнять таблицу:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline \text{1}& 2 & 2 & 5 & 7 & 11 & 16 & 28 & 39 & 62 & 90 & 140 & 202 & 308 & 448 & 0 & 308 & 795 & 795 & 1165 & 1960 & 2845\\ \hline \end{array}\] Аналогично \(R(23) = 0\).

Заполним таблицу до конца:

\[\begin {array}{|c|c|c|c|c|c|} \hline \text{22}& 23 & 24 & 25 & 26 & 27 \\ \hline \text{2845}& 0 & 2100 & 4945 & 5147 & 7247 \\ \hline \end{array}\] Отсюда получаем ответ — 7247.

Ответ: 7247

Задание 5 #12792

Исполнитель Кальк преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 2,

2. прибавить 3,

3. Прибавить 5.

Первая команда увеличивает число на экране на 2, вторая — на 3, третья — на 5. Программа для исполнителя Кальк — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 25 и при этом траектория вычислений не содержит числа 13 и 19? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 9, 12, 14.

Показать решение

Пусть \(R(n)\) — количество программ, которое число 1 преобразует в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-2) + R(n-3) + R(n-5)\)

Заполним таблицу по данной формуле до 12:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \text{1}& 0 & 1 & 1 & 1 & 3 & 2 & 5 & 6 & 8 & 14 & 16\\ \hline \end{array}\] Так как по условию сказано, что траектория не должна содержать число 13, значит \(R(13) = 0\). Продолжим заполнять таблицу:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ \hline \text{1}& 0 & 1 & 1 & 1 & 3 & 2 & 5 & 6 & 8 & 14 & 16 & 0 & 36 & 24 & 50 & 76 & 74\\ \hline \end{array}\] Аналогично \(R(19) = 0\). Заполним таблицу до конца:

\[\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|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline \text{1}& 0 & 1 & 1 & 1 & 3 & 2 & 5 & 6 & 8 & 14 & 16 & 0 & 36 & 24 & 50 & 76 & 74 & 0 & 174 & 124 & 250 & 372 & 374 & 796\\ \hline \end{array}\] Отсюда получаем ответ — 796.

Ответ: 796

Задание 6 #12794

Исполнитель Пирожок преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 3

2. Прибавить 4

3. Умножить на 2

Первая команда увеличивает число на экране на 3, вторая — на 4, третья — удваивает число. Программа для исполнителя Пирожок — это последовательность команд.

Сколько существует программ, для которых при исходном числе 256 результатом является число 273 и при этом траектория вычислений не содержит числа 262 и 270? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 10, 14, 17.

Показать решение

Пусть \(R(n)\) — количество программ, которое число 1 преобразует в число \(n\). Тогда верно следующее утверждение:

Заметим, что \(256 \cdot2 = 512\) — это больше числа, которое нам нужно найти, значит 3-я команда нам не понадобится. Составим уравнение:

\(R(n) = R(n-3) + R(n-4)\)

Составим таблицу по данному уравнению:

\[\begin {array}{|c|c|c|c|c|c|} \hline \text{256}& 257 & 258 & 259 & 260 & 261\\ \hline \text{1}& 0 & 0 & 1 & 1 & 0 \\ \hline \end{array}\] Так как траектория не должна содержать число 262, то \(R(262) = 0\). Продолжим заполнение таблицы:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{261}& 262 & 263 & 264 & 265 & 266 & 267 & 268 & 269\\ \hline \text{0}& 0 & 2 & 1 & 0 & 2 & 3 & 1 & 2\\ \hline \end{array}\] Аналогично \(R(270) = 0\).

\[\begin {array}{|c|c|c|c|c|} \hline \text{269}& 270 & 271 & 272 & 273\\ \hline \text{2}& 0 & 4 & 3 & 2 \\ \hline \end{array}\] Отсюда ответ — 2.

Ответ: 2

Задание 7 #12795

Исполнитель ЭМИ преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

3. Умножить на 2

4. Умножить на 3

Первая команда увеличивает число, записанное на экране, на 1, вторая — на 3, третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя ЭМИ — это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 45 и при этом траектория вычисления не содержит числа 5, 17 и 35? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 1314 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17, 51.

Показать решение

Пусть \(R(n)\) — количество программ, которое число 1 преобразует в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-3)\) — если число не делится ни на 2, ни на 3.

\(R(n) = R(n-1) +R(n-3) + R(n:2)\) — если число делится на 2, но не делится на 3.

\(R(n) = R(n-1) + R(n-3) + R(n:3)\) — если число делится на 3, но не делится на 2.

\(R(n) = R(n-1) + R(n-3) + R(n:2) + R(n:3)\) — если число делится и на 2, и на 3.

Сразу заметим, что по условию задачи траектория не должна содержать числа 5, 17 и 35. Значит \(R(5) = 0\), \(R(17) = 0\) и \(R(35) = 0\).

Составим таблицу по данным формулам:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{3}& 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ \hline \text{1}& 1 & 0 & 2 & 3 & 4 & 7 & 10 & 14 & 24 & 34 & 51 & 75 & 113 & 0 & 84 & 197 & 207 & 294 & 505 & 712 & 1034 \\ \hline \end{array}\] \[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{24} & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 \\ \hline \text{1034} & 1539 & 2285 & 3326 & 4916 & 7201 & 10612 & 15528 & 22842 & 33468 & 48996 & 0 & 33576 & 82572 & 82769 & 116379 \\ \hline \end{array}\] \[\begin{array}{|c|c|c|c|c|c|} \hline \text{40} & 41 & 42 & 43 & 44 & 45 \\ \hline \text{199158} & 281927 & 398651 & 597809 & 880241 & 1278967\\ \hline \end{array}\] Получаем ответ – 1278967.

Ответ: 1278967