Принцип включений–исключений в задачах на делимость
10 класс · Комбинаторика · углублённый уровень · v109
Зачем изучать
Сколько чисел делятся на 3 или на 5? Простое сложение двух количеств ошибочно: числа, кратные 15, будут сосчитаны дважды.
Определения и точные формулы
Для конечных множеств |A∪B|=|A|+|B|−|A∩B|. Среди чисел 1,…,N кратных d ровно ⌊N/d⌋. Общие кратные a и b — кратные НОК(a,b). На отрезке [L,N] количество кратных d равно ⌊N/d⌋−⌊(L−1)/d⌋.
Доказательство
Разобьём объединение на непересекающиеся части A\B, A∩B, B\A. Тогда |A|+|B| считает пересечение дважды, а |A∪B| — один раз. Поэтому вычитаем одно |A∩B|. Доказательство сохраняется и для кратных на любом конечном отрезке.
Математическая схема
Схема построена на основе указанной геометрической модели. Числовые значения извлекаются из условий, а не измеряются по рисунку.
Пример 1: выбор метода
Сколько чисел от 1 до 30 делятся на 2 или 3?
Пошаговое решение. Кратных 2 — 15, кратных 3 — 10, кратных 6 — 5. Объединение: 15+10−5=20.
Пример 2: выбор метода
Сколько чисел от 1 до 30 не делятся ни на 2, ни на 3?
Пошаговое решение. Всего 30 чисел, 20 попали в объединение предыдущего примера. Остаются 30−20=10.
Пример 3: выбор метода
Сколько чисел на [10;40] кратны 4?
Пошаговое решение. ⌊40/4⌋−⌊9/4⌋=10−2=8. Важно исключить числа ниже 10.
Типичные ошибки
- Не складывайте мощности множеств без вычитания пересечения.
- Общие кратные определяются НОК, а не произведением, если числа не взаимно просты.
- На отрезке [L,N] используйте N и L−1.
Тренировка без оценки
- Сколько чисел от 1 до 136 делятся на 5 или на 5 (хотя бы на одно)?
- Сколько чисел от 1 до 140 делятся одновременно на 6 и 6?
- Сколько чисел от 1 до 144 кратны 3, но не кратны 7?
- Сколько чисел от 1 до 148 кратны 8, но не кратны 4?
- Сколько чисел от 1 до 152 не делятся ни на 5, ни на 5?
- Сколько чисел от 1 до 156 делятся ровно на одно из чисел 6, 6?
Эти задачи имеют другие данные и не повторяют действующие оценочные варианты.
Задача на доказательство
Докажите формулу |A\B|+|B\A|=|A|+|B|−2|A∩B|.
Запишите исходные предположения и каждое преобразование; полный разбор находится в закрытом преподавательском файле.
Самостоятельная работа
Пять вариантов по десять вопросов с серверной проверкой ответов. Для бумажной работы оставлено место для решения.
Расширенный конспект (PDF) · Пять вариантов (PDF) · Решать и проверить
Итоги
Проверьте условия применимости формулы, решите один пример двумя способами и составьте контрпример к типичной ошибке. Вернитесь к теории после анализа результата самостоятельной работы.