Задача 76449

Темы:    [ Формула включения-исключения ] [ Делимость чисел. Общие свойства ] [ Классическая комбинаторика (прочее) ]

Сложность: 3 Классы: 7,8,9,10

Условие

Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7?

Решение

Сначала вычеркнем из набора чисел 1, 2, ..., 999 числа, кратные 5; их количество равно  [⁹⁹⁹/₅] = 199.  Затем из того же набора чисел 1, 2, ..., 999 вычеркнем числа, кратные 7; их количество равно  [⁹⁹⁹/₇] = 142.  При этом числа, кратные 35, будут вычеркнуты дважды. Их количество равно  [⁹⁹⁹/₃₅] = 28.  Значит, всего мы вычеркнули   199 + 142 – 28 = 313  чисел, а осталось  999 – 313 = 686 чисел.

Ответ

686 чисел.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	4
Год	1938
вариант
Тур	2
задача
Номер	4