Исполнитель меняет число командами. Нужно посчитать программы, переводящие одно число в другое с условиями на траекторию, или различные результаты программ заданной длины.
Рекуррентная формула
N(x → y) = сумма N(команда(x) → y) по всем командам.
N(y → y) = 1; если число «проскочило» y — 0.
Обязательное число z: N(a → b) = N(a → z) · N(z → b).
Запрещённые числа
Если x — запрещённое число, N(x → y) = 0.
Проверку ставим до сравнения с y, но после проверки x == y — конечное число не бывает запрещённым.
Типичные ошибки
Сложить части вместо умножения.
Для уменьшения с делением перепутать условие остановки (x < y).
Посчитать программы, а не различные результаты, или наоборот.
Разобранные варианты
Сначала реши сам — таблицей или программой, потом открой разбор.
Вариант 1
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 39 результатом является число 3, при этом траектория вычислений содержит число 28 и не содержит числа 17? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 39 траектория состоит из чисел 38, 12, 9.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 28, а числа идут по убыванию, поэтому программы считаем по частям и перемножаем: N(39 → 28) · N(28 → 3).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (17) — 0.
def f(x, y):
if x == y:
return 1
if x < y or x in (17,):
return 0
return f(x - 1, y) + f(x - 3, y) + f(x // 3, y)
print(f(39, 28) * f(28, 3))
Вариант 2
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 6 результатом является число 28, при этом траектория вычислений содержит число 26 и не содержит числа 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBC при исходном числе 6 траектория состоит из чисел 12, 15, 30.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 26, а числа идут по возрастанию, поэтому программы считаем по частям и перемножаем: N(6 → 26) · N(26 → 28).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (14) — 0.
Шаг 3. N(6 → 26) · N(26 → 28) = 668 · 1 = 668.
Ответ: 668
Решение на Python.
def f(x, y):
if x == y:
return 1
if x > y or x in (14,):
return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(6, 26) * f(26, 28))
Вариант 3
различные результаты
Исполнитель преобразует число на экране. У исполнителя есть 2 команды, которые обозначены латинскими буквами: A. Прибавить 2 B. Умножить на 3 Программа для исполнителя — это последовательность команд. Сколько различных результатов можно получить из исходного числа 4 в результате выполнения программ, содержащих ровно 11 команд?
Разбор
Идея. Программ 211 = 2048, но многие дают одинаковые числа. Удобно хранить множество чисел, достижимых за k команд, и на каждом шаге применять к каждому числу все команды. Множество само убирает повторы.
Итог: после 11 шагов в множестве 1534 различных числа.
Ответ: 1534
Решение на Python.
cur = {4}
for step in range(11):
cur = {y for x in cur for y in (x + 2, x * 3)}
print(len(cur))
Вариант 4
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 44 результатом является число 6, при этом траектория вычислений содержит число 24 и не содержит числа 13? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 44 траектория состоит из чисел 43, 39, 38.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 24, а числа идут по убыванию, поэтому программы считаем по частям и перемножаем: N(44 → 24) · N(24 → 6).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (13) — 0.
Шаг 3. N(44 → 24) · N(24 → 6) = 345 · 99 = 34155.
Ответ: 34155
Решение на Python.
def f(x, y):
if x == y:
return 1
if x < y or x in (13,):
return 0
return f(x - 1, y) + f(x - 4, y) + f(x // 3, y)
print(f(44, 24) * f(24, 6))
Вариант 5
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является число 36, при этом траектория вычислений содержит число 34 и не содержит чисел 19 и 23? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы BAC при исходном числе 5 траектория состоит из чисел 8, 9, 18.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 34, а числа идут по возрастанию, поэтому программы считаем по частям и перемножаем: N(5 → 34) · N(34 → 36).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (19 и 23) — 0.
def f(x, y):
if x == y:
return 1
if x > y or x in (19, 23,):
return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(5, 34) * f(34, 36))
Вариант 6
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 31, при этом траектория вычислений содержит число 23 и не содержит числа 22? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы BCC при исходном числе 2 траектория состоит из чисел 5, 10, 20.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 23, а числа идут по возрастанию, поэтому программы считаем по частям и перемножаем: N(2 → 23) · N(23 → 31).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (22) — 0.
def f(x, y):
if x == y:
return 1
if x > y or x in (22,):
return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(2, 23) * f(23, 31))
Вариант 7
различные результаты
Исполнитель преобразует число на экране. У исполнителя есть 2 команды, которые обозначены латинскими буквами: A. Прибавить 2 B. Умножить на 3 Программа для исполнителя — это последовательность команд. Сколько различных результатов можно получить из исходного числа 7 в результате выполнения программ, содержащих ровно 12 команд?
Разбор
Идея. Программ 212 = 4096, но многие дают одинаковые числа. Удобно хранить множество чисел, достижимых за k команд, и на каждом шаге применять к каждому числу все команды. Множество само убирает повторы.
Итог: после 12 шагов в множестве 2825 различных чисел.
Ответ: 2825
Решение на Python.
cur = {7}
for step in range(12):
cur = {y for x in cur for y in (x + 2, x * 3)}
print(len(cur))
Вариант 8
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 2 C. Найти целую часть от деления на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 26 результатом является число 2, при этом траектория вычислений содержит число 15 и не содержит чисел 22 и 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 26 траектория состоит из чисел 24, 23, 21.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 15, а числа идут по убыванию, поэтому программы считаем по частям и перемножаем: N(26 → 15) · N(15 → 2).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (22 и 11) — 0.
Шаг 3. N(26 → 15) · N(15 → 2) = 39 · 153 = 5967.
Ответ: 5967
Решение на Python.
def f(x, y):
if x == y:
return 1
if x < y or x in (22, 11,):
return 0
return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)
print(f(26, 15) * f(15, 2))
Вариант 9
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29, при этом траектория вычислений содержит числа 4 и 5 и не содержит числа 19? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACA при исходном числе 2 траектория состоит из чисел 3, 9, 10.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 4 и 5, а числа идут по возрастанию, поэтому программы считаем по частям и перемножаем: N(2 → 4) · N(4 → 5) · N(5 → 29).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (19) — 0.
def f(x, y):
if x == y:
return 1
if x > y or x in (19,):
return 0
return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)
print(f(2, 4) * f(4, 5) * f(5, 29))
Вариант 10
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 29 результатом является число 1, при этом траектория вычислений содержит число 20 и не содержит числа 19? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CCA при исходном числе 29 траектория состоит из чисел 9, 3, 2.
Разбор
Шаг 1. Разбиваем путь. Траектория обязана пройти через 20, а числа идут по убыванию, поэтому программы считаем по частям и перемножаем: N(29 → 20) · N(20 → 1).
Шаг 2. Считаем каждую часть рекурсией N(x → y) = сумма N(команда(x) → y) по всем командам; N(y → y) = 1; если перескочили y или попали в запрещённое число (19) — 0.
Шаг 3. N(29 → 20) · N(20 → 1) = 19 · 761 = 14459.
Ответ: 14459
Решение на Python.
def f(x, y):
if x == y:
return 1
if x < y or x in (19,):
return 0
return f(x - 1, y) + f(x - 3, y) + f(x // 3, y)
print(f(29, 20) * f(20, 1))
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 37, при этом траектория вычислений содержит числа 13 и 27 и не содержит чисел 23 и 32? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы BCC при исходном числе 4 траектория состоит из чисел 7, 14, 28.
Вариант 12
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 2 C. Найти целую часть от деления на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 25 результатом является число 5, при этом траектория вычислений содержит число 17 и не содержит чисел 6 и 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACA при исходном числе 25 траектория состоит из чисел 24, 12, 11.
Вариант 13
различные результаты
Исполнитель преобразует число на экране. У исполнителя есть 2 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько различных результатов можно получить из исходного числа 2 в результате выполнения программ, содержащих ровно 12 команд?
Вариант 14
увеличение · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 6 результатом является число 31, при этом траектория вычислений содержит число 22 и не содержит числа 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CAC при исходном числе 6 траектория состоит из чисел 12, 13, 26.
Вариант 15
уменьшение с делением · траектория
Исполнитель преобразует число на экране. У исполнителя есть 3 команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 2 C. Найти целую часть от деления на 3 Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 28 результатом является число 3, при этом траектория вычислений содержит числа 18 и 6 и не содержит чисел 8 и 5? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CCC при исходном числе 28 траектория состоит из чисел 9, 3, 1.