У исполнителя "Калькулятор" две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 4. Первая из них увеличивает число на экране на 1, вторая умножает его на 4. Программа для "Калькулятора" — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 32?

Пусть команда 1 это +1, а команда 2 это ×4.

Надо из 1 получить 32.

Пусть x - количество команд 1, а y - количество команд 2.

Тогда уравнение будет таким:

$$1 + x \cdot 4^y = 32$$

Или

$$x + 4^y = 31$$

Возможные варианты:

• y = 0, тогда x = 30. Программа: 111...1 (30 раз)
• y = 1, тогда x + 4 = 31, x = 27. Программа: содержит 27 команд 1 и одну команду 2. Количество вариантов: 28
• y = 2, тогда x + 16 = 31, x = 15. Программа: содержит 15 команд 1 и две команды 2. Количество вариантов: $$\frac{17!}{15!2!} = \frac{17 \cdot 16}{2} = 17 \cdot 8 = 136$$
• y = 3, тогда x + 64 = 31. Это невозможно, т.к. x должно быть отрицательным.

Итого количество программ: 1 + 28 + 136 = 165

Ответ: 165