МЕХМАТИК / Математический центр знаний и творчестваОТ ЧИСЕЛ К ИДЕЯМ · ∀ x ∈ ℝ
МехматикМатематическая библиотека
Открытое обучение
КЛАССЫ1 класс2 класс3 класс4 класс5 класс6 класс7 класс8 класс9 класс10 класс11 класс

Принцип включений–исключений в задачах на делимость

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.

Типичные ошибки

  1. Не складывайте мощности множеств без вычитания пересечения.
  2. Общие кратные определяются НОК, а не произведением, если числа не взаимно просты.
  3. На отрезке [L,N] используйте N и L−1.

Тренировка без оценки

  1. Сколько чисел от 1 до 136 делятся на 5 или на 5 (хотя бы на одно)?
  2. Сколько чисел от 1 до 140 делятся одновременно на 6 и 6?
  3. Сколько чисел от 1 до 144 кратны 3, но не кратны 7?
  4. Сколько чисел от 1 до 148 кратны 8, но не кратны 4?
  5. Сколько чисел от 1 до 152 не делятся ни на 5, ни на 5?
  6. Сколько чисел от 1 до 156 делятся ровно на одно из чисел 6, 6?

Эти задачи имеют другие данные и не повторяют действующие оценочные варианты.

Задача на доказательство

Докажите формулу |A\B|+|B\A|=|A|+|B|−2|A∩B|.

Запишите исходные предположения и каждое преобразование; полный разбор находится в закрытом преподавательском файле.

Самостоятельная работа

Пять вариантов по десять вопросов с серверной проверкой ответов. Для бумажной работы оставлено место для решения.

Расширенный конспект (PDF) · Пять вариантов (PDF) · Решать и проверить

Итоги

Проверьте условия применимости формулы, решите один пример двумя способами и составьте контрпример к типичной ошибке. Вернитесь к теории после анализа результата самостоятельной работы.

Другие уроки v109 · Предыдущий выпуск