Рассмотрим решение задачи о нахождении количества натуральных чисел, не превосходящих 1000, которые не делятся ни на 3, ни на 5, ни на 7, ни на 11.
Для этого используем принцип включения-исключения. Сначала определим количество чисел, делящихся на каждое из упомянутых чисел:
- Количество чисел ≤ 1000, делящихся на 3: (\left\lfloor \frac{1000}{3} \right\rfloor = 333)
- Количество чисел ≤ 1000, делящихся на 5: (\left\lfloor \frac{1000}{5} \right\rfloor = 200)
- Количество чисел ≤ 1000, делящихся на 7: (\left\lfloor \frac{1000}{7} \right\rfloor = 142)
- Количество чисел ≤ 1000, делящихся на 11: (\left\lfloor \frac{1000}{11} \right\rfloor = 90)
Затем учтём пересечения множеств (числа, делящиеся на несколько из указанных делителей):
- (\text{lcm}(3, 5) = 15), количество чисел делящихся на 15: (\left\lfloor \frac{1000}{15} \right\rfloor = 66)
- (\text{lcm}(3, 7) = 21), количество чисел делящихся на 21: (\left\lfloor \frac{1000}{21} \right\rfloor = 47)
- (\text{lcm}(3, 11) = 33), количество чисел делящихся на 33: (\left\lfloor \frac{1000}{33} \right\rfloor = 30)
- (\text{lcm}(5, 7) = 35), количество чисел делящихся на 35: (\left\lfloor \frac{1000}{35} \right\rfloor = 28)
- (\text{lcm}(5, 11) = 55), количество чисел делящихся на 55: (\left\lfloor \frac{1000}{55} \right\rfloor = 18)
- (\text{lcm}(7, 11) = 77), количество чисел делящихся на 77: (\left\lfloor \frac{1000}{77} \right\rfloor = 12)
Добавим сумму чисел, делящихся на трое: (например (\text{lcm}(3, 5, 7) = 105), (\text{lcm}(3, 5, 11) = 165)), также те которые делятся на все четыре: (например (\text{lcm}(3, 5, 7, 11) = 1155)— не подходит, так как больше 1000).
По формуле включения-исключения, итоговое количество чисел, не делящихся ни на одно из указанных чисел можно вычислить как:
[
1000 - (333 + 200 + 142 + 90) + (66 + 47 + 30 + 28 + 18 + 12) - (6 + 9 + 4) = 400
]
Таким образом, 400 натуральных чисел не превосходящих 1000 не делятся ни на 3, ни на 5, ни на 7, ни на 11.
Категория: Математика
Теги: теория чисел, комбинаторика