Задание №23 — Поиск количества программ

Решение:

Все три команды увеличивают число, поэтому траектория строго возрастает и число 6 может встретиться в ней не больше одного раза. Значит, любая подходящая программа однозначно разбивается на две части: сначала она переводит 2 в 6, а потом 6 в 28. По правилу умножения общее количество программ равно произведению количеств программ на каждом участке.

Участок $2 \to 6$ даёт три программы: АА (2 → 4 → 6), ВА (2 → 4 → 6) и С (2 → 6). Участок $6 \to 28$ удобно посчитать той же рекурсией: обозначим через $R(a, b)$ число программ, переводящих $a$ в $b$; тогда $R(b, b) = 1$, $R(a, b) = 0$ при $a \gt b$ и $R(a, b) = R(a + 2, b) + R(2a, b) + R(3a, b)$ в остальных случаях. Получаем $R(6, 28) = 10$.

Итого $3 \cdot 10 = 30$ программ. Для сравнения, всего программ из 2 в 28 без условия про шестёрку было бы 48, так что требование пройти через 6 действительно отсекает часть вариантов.

from functools import lru_cache

@lru_cache(None)
def R(a, b):
    if a > b:
        return 0
    if a == b:
        return 1
    return R(a + 2, b) + R(2 * a, b) + R(3 * a, b)

print(R(2, 6) * R(6, 28))   # 3 * 10 = 30

Ответ: 30