Олимпиада сириус, по математке, система счисления Назовём натуральное число интересным, если в его двоичной записи не более 2 единиц.
Например, числа 4 = 100_2 и 40 = 101000_2 — интересные, а число 14 = 1110, интересным не является. Сколько существует интересных чисел, меньших 8000?

Предыдущий
вопрос Следующий
вопрос

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

( 0 ) единиц (число ( 0 ), но мы рассматриваем только натуральные числа, поэтому оно не учитывается).( 1 ) единица (числа вида ( 2^k ), где ( k ) — неотрицательное целое число).( 2 ) единицы (числа вида ( 2^i + 2^j ), где ( i > j ) — неотрицательные целые числа).

Теперь найдем ограничение для ( k ) в случае одного нуля и двух единиц:

1. Числа с одной единицей

Числа с одной единицей в двоичной записи имеют вид ( 2^k ). Чтобы найти, какие степени подходят:

[
2^0 = 1, \
2^1 = 2, \
2^2 = 4, \
2^3 = 8, \
2^4 = 16, \
2^5 = 32, \
2^6 = 64, \
2^7 = 128, \
2^8 = 256, \
2^9 = 512, \
2^{10} = 1024, \
2^{11} = 2048, \
2^{12} = 4096, \
2^{13} = 8192 \text{ (не подходит, так как больше 8000)}.
]

Таким образом, подходящие степени с одной единицей — это ( k = 0 ) до ( k = 12 ). Всего таких чисел ( 12 + 1 = 13 ).

2. Числа с двумя единицами

Для чисел с двумя единицами, они могут быть записаны как ( 2^i + 2^j ) с ( i > j ). Чтобы найти числа, подходящие под это условие, мы рассмотрим пару ( (i, j) ) и найдем максимальные значения для каждого:

Максимальное значение ( 2^i + 2^j < 8000 ) означает, что:

( i ) — максимальная степень двойки, которая может быть не менее ( 0 ).( j ) — соответственно, должно быть меньше ( i ).

Исходя из предела ( 2^k < 8000 ):

[
2^{12} = 4096, \
2^{13} = 8192 \text{ (не подходит)}.
]

Таким образом ( i ) может быть от ( 1 ) до ( 12 ) (степени от ( 1 ) до ( 12 ), поскольку ( 2^0 ) ( (1) ) не учитывается, так как числа должны быть интересными).

Теперь, мы будем рассчитывать количество этих пар ( (i, j) ):

Для каждого ( i ) от ( 1 ) до ( 12 ) возможных ( j < i ) будет ( i - 1 ).

Считаем пары:

Для ( i = 2 ): ( j = 1 ) ( \rightarrow 1 ) пара.Для ( i = 3 ): ( j = 1, 2 ) ( \rightarrow 2 ) пары.Для ( i = 4 ): ( j = 1, 2, 3 ) ( \rightarrow 3 ) пары.
...

Если можем просуммировать это:

[
(1 + 2 + 3 + 4 + \ldots + 11) = \frac{11 \times 12}{2} = 66.
]

Итог

Теперь мы можем сложить количество интересных чисел:

Числа с одной единицей: ( 13 )Числа с двумя единицами: ( 66 )

В итоге:

[
13 + 66 = 79.
]

Таким образом, количество интересных чисел, меньших 8000, равно ( \boxed{79} ).