ЗАДАНИЕ 15 Введите ответ в числовое поле Исполнитель ГОСТ преобразует число, записанное на экране в троичной системе счисления. У исполнителя ГОСТ есть две команды, которым присвоены номера: 1. Умножь на 2 2. Умножь на 2 и прибавь 1 Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 15 команд?

Решение:

Обозначим через a - команду "умножь на 2", а через b - команду "умножь на 2 и прибавь 1". Тогда, программа, содержащая 15 команд, будет представлять собой последовательность из 15 символов, каждый из которых либо a, либо b.

Минимальный результат будет, если все 15 команд будут типа a (умножить на 2):

$$1 \cdot 2^{15} = 32768$$

Максимальный результат будет, если все 15 команд будут типа b (умножить на 2 и прибавить 1):

Обозначим результат после n-ой команды как $$x_n$$. Тогда $$x_0 = 1$$, и $$x_n = 2x_{n-1} + 1$$.

$$x_1 = 2 \cdot 1 + 1 = 3$$ $$x_2 = 2 \cdot 3 + 1 = 7$$ $$x_3 = 2 \cdot 7 + 1 = 15$$

Заметим, что $$x_n = 2^{n+1} - 1$$.

Тогда, если все 15 команд типа b, то результат будет:

$$x_{15} = 2^{16} - 1 = 65535$$

Теперь нужно понять, какие значения между 32768 и 65535 могут быть получены.

Пусть у нас k команд типа b и 15-k команд типа a. Заметим, что каждая команда типа b добавляет 1 к результату после умножения на 2.

Результат можно представить как:

$$1 \cdot 2^{15} + \sum_{i=1}^{k} 2^{j_i}$$, где $$j_i$$ - это степени, соответствующие позициям команд типа b.

Таким образом, нужно понять, сколько различных значений может принимать сумма $$\sum_{i=1}^{k} 2^{j_i}$$, где k может быть от 0 до 15, а $$j_i$$ - различные числа от 0 до 14.

Каждое число от 0 до $$2^{15}-1$$ можно представить в виде суммы различных степеней двойки. Следовательно, все числа от $$2^{15}$$ до $$2^{16}-1$$ можно получить. Таким образом, количество различных результатов равно $$16$$.

Ответ: 16