Назовём натуральное число интересным, если в его двоичной записи не более 2 единиц. Например, числа 4 100 и 40 101000 интересные, а число 14 1110, интересным не является. Сколько существует интересных чисел, меньших 1000?
Чтобы определить, сколько существует интересных натуральных чисел, меньших 1000, нужно сначала понять, что интересное число в двоичной системе счисления может иметь не более 2 единиц. Это значит, что такие числа могут быть представлены в виде:
- Один 1 (все остальные биты — 0).
- Два 1, которые могут находиться на разных позициях.
Теперь давайте более подробно рассмотрим каждую категорию.
Числа с одной 1. В двоичной записи это будут числа, которые равны степени двойки. Такие числа выглядят так:
- 2^0 = 1 (1 в двоичной системе: 1)
- 2^1 = 2 (10)
- 2^2 = 4 (100)
- 2^3 = 8 (1000)
- 2^4 = 16 (10000)
- 2^5 = 32 (100000)
- 2^6 = 64 (1000000)
- 2^7 = 128 (10000000)
- 2^8 = 256 (100000000)
- 2^9 = 512 (1000000000)
Однако число 2^10 = 1024 уже больше 1000, поэтому мы учитываем только числа до 2^9. В этом случае у нас 9 интересных чисел: 1, 2, 4, 8, 16, 32, 64, 128 и 256.
Числа с двумя 1. Такие числа можно получить, выбирая разные позиции для единиц. Нам нужно выбрать 2 позиции из 10 возможных (поскольку 999 в двоичной системе занимает 10 бит). Это можно сделать с помощью комбинаций.
Формула для нахождения количества комбинаций:
\[ C(n, k) = \frac{n!}{k!(n-k)!} \]
Где \( n \) — количество бит (в нашем случае 10), а \( k \) — количество единиц (в нашем случае 2).
Подставим значения: \[ C(10, 2) = \frac{10!}{2!(10-2)!} = \frac{10 \times 9}{2 \times 1} = 45 \]
Теперь суммируем количество интересных чисел:
- Числа с одной 1: 9
- Числа с двумя 1: 45
Таким образом, общее количество интересных чисел, меньших 1000, составляет:
\[ 9 + 45 = 54 \]
Ответ: 54 интересных числа меньше 1000.
