31. Включения и исключения через свойства
Принцип включений и исключений часто применяют так: нужно посчитать объекты, у которых нет ни одного из заданных «нежелательных» свойств. Для каждого набора из свойств считаем объекты, обладающие сразу всеми свойствами набора, и складываем эти числа по всем наборам — получаем число . Тогда ответ равен .
Что пригодится из прошлого: формула для множеств — это та же формула на другом языке; следствия бинома — знакопеременная сумма ; включения и исключения для трёх множеств. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Язык свойств
Пусть — множество объектов, а — набор свойств, которыми объекты могут обладать (или не обладать). Примеры: объекты — числа от до , свойство — «делится на », — «делится на », — «делится на ».
Введём обозначения:
- — число объектов, обладающих свойством ();
- — число объектов, обладающих обоими свойствами и ();
- — число объектов, обладающих всеми этими свойствами;
- — число объектов, обладающих всеми свойствами.
Теперь соберём одинаковые по размеру наборы:
Теорема (принцип включений и исключений). Если — число объектов множества , не обладающих ни одним из свойств , то
Здесь — число объектов, у которых ровно свойств (буква — от английского exactly, «ровно»). Обратите внимание на два смысла буквы : — число объектов (в скобках перечислены свойства), а с целым номером — сумма таких чисел по всем наборам из свойств.
Связь с прошлой главой. Пусть — объекты со свойством . Тогда , а — сумма размеров пересечений по всем наборам из множеств. Объекты без ни одного свойства — , их . Подставим формулу для объединения:
Это то же утверждение, только в более удобной записи.
Что такое : сколько раз учитывается объект
Число — это не число объектов «с одним свойством». Объект, у которого свойств, участвует в ровно раз (по разу на каждое своё свойство). В он участвует раз — по разу на каждую пару своих свойств, в — раз.
Вернёмся к классу из прошлой главы: математику любят , физику , химию человек и так далее; восстановленная карта областей показала человека без любимых предметов, с ровно одним, с ровно двумя, с тремя. Подсчитаем, сколько раз учтён каждый:
Каждый человек, у которого ровно свойств (любимых предметов), входит в ровно раз (это первый множитель в каждом произведении ниже):
- : 3 чел.; учтены в — 1 · 3 = 3, в — 0 · 3 = 0, в — 0 · 3 = 0, в — 0 · 3 = 0
- : 14 чел.; учтены в — 1 · 14 = 14, в — 1 · 14 = 14, в — 0 · 14 = 0, в — 0 · 14 = 0
- : 11 чел.; учтены в — 1 · 11 = 11, в — 2 · 11 = 22, в — 1 · 11 = 11, в — 0 · 11 = 0
- : 2 чел.; учтены в — 1 · 2 = 2, в — 3 · 2 = 6, в — 3 · 2 = 6, в — 1 · 2 = 2
Получаем , , , . Тогда
то есть три человека не любят ни одного предмета. Совпало с прошлым ответом.
Доказательство
Докажем теорему индукцией по числу объектов .
База. Если , то и все : равенство верно.
Шаг. Любое конечное множество получается из пустого добавлением объектов по одному, поэтому достаточно проверить шаг. Допустим, равенство верно для множества . Добавим новый объект и проверим, что обе части равенства изменятся на одно и то же число. Пусть объект обладает свойствами из .
- , то есть не обладает ни одним свойством. Тогда увеличивается на . Правая часть: тоже увеличивается на ; остальные не меняются, ведь у нет ни одного свойства. Обе части выросли на .
- . Объект обладает свойством, поэтому не меняется. А увеличивается на число наборов из свойств, которыми обладает: на при и на при . Правая часть меняется на
(это по формуле бинома, см. следствия бинома; здесь ). Правая часть не изменилась — как и левая.
Значит, равенство сохраняется при добавлении любого объекта.
Как решать задачи
- Определите объекты и «нежелательные» свойства .
- Найдите : сколько объектов обладает заранее выбранными свойствами (если для всех наборов получилось одно и то же число, умножьте его на число наборов ).
- Подставьте в
Пример. Числа, не делящиеся на , и . Сколько чисел от до не делятся ни на , ни на , ни на ? Свойства — «делится на », «на », «на ».
Напомним: — целая часть числа , то есть наибольшее целое число, не превосходящее . Среди чисел от до ровно кратны .
- .
- .
- (число делится на и тогда и только тогда, когда делится на ; для и — на ; для и — на ).
- .
Тогда . Вот эти числа: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97.
Частые ошибки
- Считать числом объектов ровно с одним свойством. Объект с свойствами учтён в ровно раз.
- Обрывать сумму. После нужно продолжать: до .
- Потерять знаки. Знак перед равен .
- Считать число кратных нескольким числам сразу по одному. Для делимости на несколько простых чисел делят на их произведение: , а не .
Проверь себя
1. Сколько чисел от до не делятся ни на , ни на , ни на ?
Решение
; ; ; . .
2. Сколько чисел от до не делятся ни на , ни на ?
Решение
, , . .
3. Известно: , , , . Сколько объектов не обладают ни одним из трёх свойств?
Решение
.
4. Объект обладает свойствами из . В скольких слагаемых он участвует?
Решение
В каждой паре из его свойств: раз.
Итог
- Свойства ; — сумма по всем наборам из свойств числа объектов, обладающих сразу всеми свойствами набора; .
- — число объектов без единого свойства.
- Доказательство: добавление объекта с свойствами меняет правую часть на (для ).
- Объект с свойствами учтён в ровно раз.
