Номер 7, страница 297 - гдз по алгебре 9 класс учебник Мерзляк, Полонский

7. Формула включений и исключений

Рекомендуемая литература

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. — М. : ФИМА, МЦНМО, 2006.

Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. — Киров : АСА, 1984.

Горбачёв Н.В. Сборник олимпиадных задач по математике. — М. : МЦНМО, 2004.

Яглом И. Заплаты на кафтане // Квант. — 1974. — № 2.

Формула включений и исключений (или принцип включений-исключений) — это комбинаторная формула, позволяющая определить мощность (количество элементов) объединения нескольких конечных множеств. Суть принципа заключается в том, чтобы найти количество элементов, входящих хотя бы в одно из этих множеств, зная размеры самих множеств и размеры всех их возможных пересечений. Идея состоит в том, чтобы сначала сложить размеры всех множеств, затем вычесть размеры всех попарных пересечений, затем прибавить размеры всех тройных пересечений, и так далее, чередуя знаки.

Для двух конечных множеств $A$ и $B$ количество элементов в их объединении $A \cup B$ можно найти, сложив их мощности и вычтя мощность их пересечения. Это необходимо, поскольку элементы, находящиеся в пересечении $A \cap B$, при простом сложении $|A| + |B|$ учитываются дважды — один раз как элементы $A$ и один раз как элементы $B$. Чтобы исправить это, мы вычитаем их количество один раз.

Ответ: $|A \cup B| = |A| + |B| - |A \cap B|$

Для трех множеств $A$, $B$ и $C$ формула усложняется. Сначала мы складываем мощности всех трех множеств: $|A| + |B| + |C|$. При этом элементы, принадлежащие пересечениям двух множеств (например, $A \cap B$), посчитаны дважды, а элементы, принадлежащие пересечению всех трех множеств ($A \cap B \cap C$), посчитаны трижды. Чтобы это исправить, мы вычитаем мощности всех попарных пересечений: $- (|A \cap B| + |A \cap C| + |B \cap C|)$. Теперь элементы из попарных пересечений (но не из тройного) посчитаны ровно один раз. А элементы из тройного пересечения $A \cap B \cap C$ были трижды добавлены (в сумме $|A|+|B|+|C|$) и трижды вычтены (в сумме попарных пересечений), то есть их текущий вклад равен нулю. Поэтому их нужно добавить один раз, прибавив $|A \cap B \cap C|$.

Ответ: $|A \cup B \cup C| = (|A| + |B| + |C|) - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$

Этот принцип можно обобщить на случай $n$ конечных множеств $A_1, A_2, \dots, A_n$. Мощность их объединения равна сумме мощностей всех множеств, минус сумма мощностей всех попарных пересечений, плюс сумма мощностей всех тройных пересечений, и так далее, со знакопеременным рядом до пересечения всех $n$ множеств. В общем виде формула выглядит так:

Ответ: $|\bigcup_{i=1}^{n} A_i| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|$

Рассмотрим классическую задачу: сколько натуральных чисел от 1 до 100 не делятся ни на 2, ни на 3, ни на 5? Пусть $U$ — множество всех натуральных чисел от 1 до 100, $|U| = 100$. Обозначим свойства: $P_2$ — число делится на 2, $P_3$ — число делится на 3, $P_5$ — число делится на 5. Пусть $A_k$ — подмножество $U$, элементы которого обладают свойством $P_k$. Мы ищем количество чисел, не обладающих ни одним из этих свойств, то есть $|U| - |A_2 \cup A_3 \cup A_5|$. Сначала найдем $|A_2 \cup A_3 \cup A_5|$ по формуле включений и исключений для трех множеств.

Мощности одиночных множеств:
$|A_2| = \lfloor\frac{100}{2}\rfloor = 50$
$|A_3| = \lfloor\frac{100}{3}\rfloor = 33$
$|A_5| = \lfloor\frac{100}{5}\rfloor = 20$
Мощности попарных пересечений (числа, делящиеся на оба числа, т.е. на их наименьшее общее кратное):
$|A_2 \cap A_3| = |A_6| = \lfloor\frac{100}{6}\rfloor = 16$
$|A_2 \cap A_5| = |A_{10}| = \lfloor\frac{100}{10}\rfloor = 10$
$|A_3 \cap A_5| = |A_{15}| = \lfloor\frac{100}{15}\rfloor = 6$
Мощность тройного пересечения:
$|A_2 \cap A_3 \cap A_5| = |A_{30}| = \lfloor\frac{100}{30}\rfloor = 3$
Теперь применяем формулу:
$|A_2 \cup A_3 \cup A_5| = (|A_2| + |A_3| + |A_5|) - (|A_2 \cap A_3| + |A_2 \cap A_5| + |A_3 \cap A_5|) + |A_2 \cap A_3 \cap A_5|$
$|A_2 \cup A_3 \cup A_5| = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74$.
Это количество чисел, которые делятся хотя бы на одно из чисел 2, 3 или 5. Чтобы найти количество чисел, которые не делятся ни на одно из них, вычтем это значение из общего количества чисел:
$100 - 74 = 26$.

Ответ: 26 чисел от 1 до 100 не делятся ни на 2, ни на 3, ни на 5.