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

Переход к дополнению

Простейшим примером «метода решета» является переход к дополнению: число «хороших» элементов равно общему числу элементов минус число «плохих» элементов.

Задача. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна цифра 7?

Решение. Найдём сначала, сколько всего имеется четырёхзначных чисел. Первую цифру мы можем выбрать девятью способами, каждую из остальных цифр — десятью. Стало быть, количество четырёхзначных чисел равно 9 · 10 · 10 · 10 = 9000.

Теперь найдём, сколько четырёхзначных чисел не содержат ни одной семёрки. Для выбора первой цифры имеется 8 способов, для выбора каждой из остальных цифр — 9 способов. Следовательно, всего будет 8 · 9 · 9 · 9 = 5832 четырёхзначных чисел, в записи которых нет ни одной цифры 7.

Ну а чисел, в которых хотя бы одна семёрка имеется, будет 9000 − 5832 = 3168.

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

Действуя по схеме «ни одного» равно общему числу минус «хотя бы один», мы должны уметь вычислять «хотя бы один», то есть находить число объектов, обладающих хотя бы одним из указанных свойств. С теоретико-множественной точки зрения речь идёт о нахождении числа элементов в объединении нескольких множеств. В такой ситуации часто приходит на помощь формула включений и исключений.

Задача. Каждый ученик класса побывал в театре или в кино. В театр сходили 22 человека. В кино были 15 человек. И в театре, и в кино были 7 человек. Сколько учеников в классе?

Решение. Если мы найдём сумму 22 + 15, то окажется, что каждого, кто побывал и в театре, и в кино, мы посчитали дважды (например, если Вася сходил и в театр, и в кино, то один раз он вошёл в эту сумму в числе 22 «театралов», а второй раз — в числе 15 «киношников»). Поэтому найденная сумма на 7 больше количества учеников в классе. Следовательно, в классе 22 + 15 − 7 = 30 человек.

Формула включений и исключений для двух множеств. Для любых конечных множеств A и B справедливо равенство

|A ∪ B| = |A| + |B| − |A ∩ B|.

ЗАДАЧИ

1. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна чётная цифра?

8375

2. Сколько существует шестизначных чисел, в записи которых есть хотя бы две одинаковых цифры?

763920

3. Сколько существует пятизначных чисел, в записи которых есть хотя бы две единицы?

7623

4. В саду у Ани и Вити росло 2006 розовых кустов. Витя полил половину всех кустов, и Аня полила половину всех кустов. При этом оказалось, что ровно три куста, самые красивые, были политы и Аней, и Витей. Сколько розовых кустов остались не политыми?

5. По данным опроса, проведённого в 7 «Е» классе, выяснилось, что 20% учеников, интересующихся математикой, интересуются ещё и физикой, а 25% учеников, интересующихся физикой, интересуются также и математикой. И только Пете с Васей не интересен ни один из этих предметов. Сколько человек в 7 «Е», если известно, что их больше 20, но меньше 30?

6. Пусть A — множество букв слова «абракадабра», B — множество букв слова «бригантина», C — множество букв слова «каракатица». Выпишите множества A, B и C, найдите их всевозможные пересечения и проверьте формулу включений и исключений для трёх множеств.

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

686

8. Сколько чисел из набора 1, 2, . . . , 2010, 2011 не делятся ни на 3, ни на 7?

1149

9. На столе рубашкой вверх была разложена колода из 36 игральных карт. Лёша перевернул 30 карт, затем Макс перевернул 19 карт, а после этого Боря — 21 карту. В результате вся колода оказалась рубашкой вниз. Сколько карт было перевёрнуто трижды?

10. Трое ребят принялись красить лист ватмана, каждый — в свой цвет. Один закрасил красным 75% листа, второй закрасил зелёным 70% листа, а третий закрасил синим 65% листа. Сколько процентов листа будет заведомо закрашено всеми тремя цветами?

10%

11. Найдите количество натуральных делителей числа N = 1 00 . . . 0 | {z } 40 , а) не являющихся ни точными квадратами (т. е. квадратами натуральных чисел), ни точными кубами; б) не представимых в виде mn , где m и n — натуральные числа, причём n > 1.

а) 1093; б) 981

12. В группе 17 человек знают английский язык, 14 человек знают китайский язык, 20 человек знают арабский язык и 19 человек знают польский язык. При этом 34 человека в группе знают ровно один язык из перечисленных, а остальные — ровно два языка из перечисленных. Сколько человек в группе? 52

13. В группе 15 человек знают английский язык, 16 человек знают китайский язык, 20 человек знают арабский язык и 21 человек знает польский язык. В группе нет людей, знающих три языка, и 23 человека в группе знают ровно два языка из перечисленных. Сколько человек в группе знают ровно один язык из перечисленных?

14. В стране шесть городов: А, Б, В, Г, Д и Е. Их хотят связать пятью авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать?

1296

15. В классе 20 учеников, каждый из которых дружит ровно с шестью одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся.

360

16. Класс из 20 учеников разделён на две половины так, что каждый школьник из первой половины дружит ровно с шестью одноклассниками, а каждый школьник из второй половины дружит ровно с четырьмя одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся.

450

17. Прямоугольный параллелепипед 35 × 40 × 56, разбитый на 78400 единичных кубиков, проткнули иглой по его диагонали. Сколько единичных кубиков протыкает игла?

112

18. Уходя на работу, мама поручила Мише, Пете и Васе: а) подмести пол в прихожей; б) помыть посуду; в) купить хлеба; г) заплатить за электричество; д) вынести мусор; е) пропылесосить ковёр в гостиной. Сколькими различными способами они могут распределить задания так, чтобы каждое задание делал кто-то один из ребят и при условии, чтобы каждый что-нибудь делал?

540