Question

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

1. прибавь 1
2. прибавь 5

Первая команда увеличивает число на экране на 1, вторая — на 5. Программа для Удвоителя — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 15?

Accepted Answer

20

Answer

Идея решения: найти все комбинации команд, которые дают требуемую сумму, и подсчитать количество различных порядков их расположения.

Нужно увеличить число с 2 до 15, то есть добавить 13. Обозначим количество команд первого типа (прибавь 1) как $a$, а количество команд второго типа (прибавь 5) как $b$. Тогда:

$$a + 5b = 13$$

Так как $a, b \geq 0$, найдём все решения:
- $b = 0$: $a = 13$ (набор из 13 единиц)
- $b = 1$: $a = 8$ (набор из 1 пятёрки и 8 единиц)
- $b = 2$: $a = 3$ (набор из 2 пятёрок и 3 единиц)
- $b \geq 3$: решений нет (так как $5 \cdot 3 = 15 > 13$)

Для каждого решения подсчитаем количество различных расположений команд (перестановки с повторениями):

1. $(a, b) = (13, 0)$: $\frac{13!}{13! \cdot 0!} = 1$ программа

2. $(a, b) = (8, 1)$: $\frac{9!}{8! \cdot 1!} = 9$ программ

3. $(a, b) = (3, 2)$: $\frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = 10$ программ

Всего: $1 + 9 + 10 = 20$ программ.

Проверка рекурсивным перебором:

```python
def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    return f(x + 1, y) + f(x + 5, y)

print(f(2, 15))
```

Задание №23Алгоритмы и исполнителиЕГЭ по информатике