Конечные множества. 1.2.1. Формула включений-исключений (число элементов в объединении конечных множеств)

1.2.1. Формула включений-исключений (число элементов в объединении конечных множеств)

Рассмотрим предложения, которые позволят находить число элементов в объединении конечного числа конечных множеств.

Теорема 1. Если пересечение конечных множеств и В пусто ( AÇ B =Æ ), то число элементов в их объединении равно сумме чисел элементов множеств А и В:

ê.

Действительно, пусть множество А содержит m элементов, а множество В – n элементов, причем среди них нет совпавших. Тогда для получения множества АÈ В надо взять все элементов множества А и добавить к ним все n элементов множества В. Поскольку в множествах и нет общих элементов, то множество будет содержать элементов.

Теорема 2. Для любых конечных множеств А и В верно равенство

ê ê = ç ç+ç ç- ç ç,

Доказательство. Множество АÈ В является объединением трех попарно непересекающихся множеств: , и . Первое из этих множеств содержит çА ç - çA Ç Bç элементов, второе содержит çВ ç - çA Ç Bç элементов, а третье - çA Ç Bç элементов. Значит, число элементов в множестве АÈ В равно

çА ç-çAÇBç+çВ ç-çAÇBç+çAÇBç, то есть êАÈ В ê = çА ç+çВ ç-çA Ç Bç.

Полученная формула является частным случаем более общей формулы

çA₁ È A₂ È …È A_m ç = çA₁ç+ çA₂ ç+… çA_m ç - çA₁ Ç A₂ç - çA₁Ç A₃ç -….- çA₁ Ç A _mç-

çA₂ Ç A₃ç -… - çA₂ Ç A _mç -… - çA _{m -1} Ç A _m ç + çA₁ Ç A₂Ç A₃ç +….+ (-1)^k+1 çA₁ Ç …Ç A_k ç + …(-1)^m+1 çA₁Ç …ÇA_m ç, которую называют формулой включений и исключений. В эту формулу, кроме самих множеств A_1,A_2,… A_m, входят их всевозможные пересечения по 2, по 3,…, по m множеств. При этом, если число пересекаемых множеств нечетно, то соответствующее слагаемое входит в формулу со знаком «плюс», а если оно четно, – то со знаком «минус».

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

Задача. В результате опроса 76 школьников выяснилось, что 45 занимаются в кружке по рисованию, 31 - в танцевальном кружке, 52 - в кружке «умелые руки». Три кружка посещают 8 школьников; кружки по рисованию и «умелые руки» - 28; кружки по рисованию и танцевальный - 16; танцевальный кружок и кружок «умелые руки» - 20. Сколько школьников из опрошенных не занимаются ни в одном кружке ?

Решение. Пусть А –- множество тех школьников из 76 опрошенных, которые занимаются в кружке по рисованию, В – множествошкольников, занимающихся в танцевальном кружке, а С – в кружке «умелые руки». Тогда все эти множества являются подмножествами множества U всех опрошенных школьников. По условию задачи çU ç = 76,

çА ç= 45, çВ ç = 31, çС | = 52. Так как школьник, посещающий кружки по рисованию и «умелые руки», принадлежит и множеству А, и множеству С, а значит, принадлежит множеству А Ç С, то по условию задачи, êАÇС ê = 28. Аналогично, êАÇ В ê = 16, çВÇ С ç = 20, çАÇ ВÇ С ç = 8. Изобразим рассматриваемые множества с помощью диаграммы Эйлера - Венна.

Как показывает диаграмма, ç, . Тогда çК ç = çАÈВÈСç = çАç + çXç + |У| = çА ç + çB ç - çAÇB ç + | C | - çAÇC | - | ВÇС ç + çАÇВÇС | = çА ç+ çB ç+ | C ç - çA Ç B ç - çA ÇC| - В Ç С ç + çАÇВÇС ç. Таким образом,

çАÈВÈС ç = çА ç + çB ç + |C ç - çA Ç B) ç - çA ÇC | - | В Ç С ç + çАÇВÇС ç.

Подставим в полученную формулу данные из условия задачи:

çК ç= 45+31+52 – 16 – 28 – 20 + 8 = 72 . Итак, 72 школьника занимаются хотя бы в одном кружке. Тогда çТ ç = çU ç - çК ç = 76 - 72 = 4.

Ответ: 4 школьника не занимаются ни в одном кружке.

24.В СИЗО находится 20 человек. Из них 10 человек задержаны по статье , 12 человек задержаны по статье и 7 человек по статье . Известно также, что по статьям и в СИЗО находятся 8 человек, по статьям и 3 человека, и — 4 человека, а два человека — по всем трем статьям.

а) Сколько человек задержано ровно по двум статьям?

б) Сколько человек задержано только по одной статье?

в) Сколько человек задержано по другим статьям?

Решение.

Первый способ.

Нам известно, что |А| = 10, |В| = 12, |С| = 7, |А Ç В| =8, |В Ç С| = 4, |А Ç С| = 3,

|А Ç В Ç С| = 2.

а) Сначала найдем количество человек, задержанных только по статьям и :

|(А Ç В) \ (А Ç В Ç С)| = | А Ç В | - | А Ç В Ç С | = 8 - 2 = 6.

Число людей, задержанных по статьям и , равно

|(А Ç С) \ (А Ç В Ç С)| = 3 - 2 = 1,

задержанных по статьям и , – равно

|(В Ç С) \ (А Ç В Ç С)| = 4 - 2 = 2.

Тогда ровно по двум статьям задержаны 6 + 2 + 1 = 9 (человек).

б) Выясним, сколько человек задержаны только по статье :

|А \ (А Ç В) \ (А Ç С)| = |А| - | А Ç В | - | А Ç С | + | А Ç В Ç С | = 10 - 8 - 3 + 2 = 1.

Определим, сколько имеется задержанных по статье :

|В \ (А Ç В) \ (В Ç С) | = 12 - 8 - 4 + 2 = 2.

Установим число задержанных по статье :

| С \ (А Ç С) \ (В Ç С) | = 7 - 3 - 4 + 2 = 2.

Таким образом, только по одной статье задержано 1 + 2 + 2 = 5 (человек).

в) Найдем, сколько человек задержаны хотя бы по одной из статей , и .

Разобьем множество людей, задержанных хотя бы по одной из статей , и на три не пересекающихся подмножества: множество людей, задержанных ровно по трем статьям, ровно по двум статьям, точно по одной статье. Первому множеству принадлежит 2 человека, второму — 9, третьему —5. Сумма этих чисел даст искомое число: 2 + 9 + 5 = 16. Таким образом, по другим статьям в СИЗО находятся 20 - 16 = 4 человека.

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

Исходя из условия задачи, изобразим основное множество, множество всех людей, находящихся в СИЗО, в виде прямоугольника, а его подмножества (подмножества , и – множества людей, задержанных по соответствующим статьям), в виде кругов. Таким образом получим диаграмму Эйлера-Венна, иллюстрирующую условие задачи (рис.1): диаграмма показывает взаимосвязи между множествами, о которых идет речь в задаче. Далее, используя условие задачи, можно определить число элементов в каждом из подмножеств, изображаемых криволинейными областями внутри кругов, и ответить на все поставленные вопросы.

а) Сколько студентов не посещают ни уголовного права, ни муниципального права, ни математики?

б) Сколько студентов посещают только один из трех предметов?

в) Сколько студентов посещают ровно два предмета?

26. В экзаменационную сессию студенты сдавали три экзамена: по истории, по философии и по социологии. Из 172 студентов экзамен по истории сдали 110 человек, по философии - 100, по социологии - 80. При этом экзамены по истории и философии сдали 60 студентов, экзамены по истории и социологии - 50, по философии и социологии - 40; 30 студентов сдали все три экзамена. Сколько студентов не сдали ни одного экзамена ? Сколько студентов сдали экзамены по истории и философии, но не сдали экзамен по социологии ?

27. Из 100 учеников гимнастикой занимается 28 человек, волейболом – 42, плаванием – 30; гимнастикой и волейболом занимается 10 человек, гимнастикой и плаванием – 8, волейболом и плаванием – 5. Всеми тремя видами спорта занимается 3 ученика. Сколько учеников не занимается спортом ? Сколько учеников занимается только гимнастикой? Только плаванием? Сколько учеников занимается ровно двумя видами спорта?

28.На кафедре иностранных языков работают несколько преподавателей. Из них 6 человек преподают английский язык, б – немецкий язык и 7 – французский; 4 работника кафедры преподают английский и немецкий языки, 3 – немецкий и французский, 2 – французский и английский, 1 – все три языка. Сколько человек работает на кафедре? Сколько из них преподают только английский язык? Только французский язык?

29.При опросе 30 детей выяснилось, что каждый из них коллекционирует марки, значки или открытки, причем марки коллекционирует 21 ребенок, значки – 18, открытки – 15, марки и значки – 11, марки и открытки – 9, значки и открытки – 7. Сколько детей коллекционирует и марки, и значки, и открытки? Сколько детей коллекционирует только значки?

30. Из 100 студентов 24 не изучают никакого языка; 26 – немецкий, 48 – французский, 8 – немецкий и французский. Сколько студентов изучают только английский язык ?

31.После экзаменационной сессии оказалось, что 10 студентов второй группы имеют в зачетных книжках хотя бы одну оценку «отлично», 20 студентов – хотя бы одну оценку «хорошо», 10 – хотя бы одну оценку «удовлетворительно». При этом «пятерки» и «четверки» имеются у пяти студентов, «пятерки» и «тройки» – у трех студентов, «четверки» и «тройки» – у четырех студентов, а два студента имеют в зачетныхкнижках и «пятерки», и «четверки», и «тройки». Сколько студентов во второй группе, если известно, что никто во время сессии не получил оценку «неудовлетворительно» ?

32.В результате опроса 60 посетителей библиотеки выяснилось, что 25 человек предпочитают детективы, 21–- фантастику, 18 – исторические романы, причем 5 человек из опрошенных любят детективы и исторические романы, 5 – детективы и фантастику, б – исторические романы и фантастику, а двум посетителям нравятся и детективы, и фантастика, и исторические романы.

Сколько человек из опрошенных не отдают предпочтение перечисленным выше жанрам ?

33.Из 73 школьников в волейбол играют 52, в футбол – 45, в баскетбол – 31. Во все три игры играют 8 ребят, в волейбол и футбол – 28, в волейбол и баскетбол – 20, в футбол и баскетбол – 16. Сколько школьников играют только в баскетбол ? только в футбол?

34.В классе 25 учащихся. Из них лыжников 13, пловцов 8, велосипедистов 17, причем каждый спортсмен занимается только двумя видами спорта и учится на «З» и «4». В классе 6 отличников. Сколько в классе спортсменов?

35.В отчете об обследовании 100 студентов сообщалось, что количество студентов, изучающих различные языки таково: английский язык изучают 30 человек, французский – 50, немецкий – 23, французский и английский – 8, немецкий и французский – 20, немецкий и английский – 10, все три языка – 5 человек. Отчет не был принят . Почему ?

36.В СИЗО находится 20 человек. Известно, что: из них 10 человек задержаны по статье А, 12 задержаны по статье В и 7 – по статье С, по статьям А и В в СИЗО находится 8 человек, по статьям А и С – 3 человека, по статьям В и С – 4 человека, а 2 человека задержаны по всем трем статьям. а) Сколько человек задержаны ровно по двум статьям? б) Сколько человек задержаны только по одной статье? в) Сколько человек задержаны по другим статьям?

37.Из потока в 100 студентов 63 студента посещают лекции по уголовному праву,39 – по муниципальному праву и 72 – по математике. Известно также,что 44 студента посещают уголовное праао и математику, 25 – математику и муниципальное право, 20 – муниципальное право и уголовное право. Кроме того, 13 студентов успевают ходить на занятия по всем трем предметам. а) Сколько студентов не посещают занятия ни по уголовному праву, ни по муниципальному праву, ни по математике? б) Сколько студентов посещают занятия только по одному из трех предметов? в) Сколько студентов посещают ровно два предмета?

38.Староста одного класса дал следующие сведения об учениках: В классе учатся 45 школьников, в том числе 25 мальчиков. 30 школьников учатся на «хорошо» и «отлично», в том числе 16 мальчиков. Спортом занимаются 28 учащихся, в том числе 18 мальчиков и 17 школьников, учащихся на «хорошо» и «отлично». 15 мальчиков учатся на «хорошо» и «отлично» и занимаются спортом. Докажите, что в этих сведениях есть ошибка.

39.Сколько чисел среди первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни на 5?

40.Сколько чисел среди первой тысячи натуральных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 7?

41.Из 36 человек, которые учились по специальности «теоретическая физика» во время каникул только двое не были ни в кино, ни в театре, ни в цирке. В кино побывало 25 человек, в театре – 11, в цирке – 17, в кино и театре – 6, в кино и цирке – 10, в театре и цирке – 4. Определите, есть ли студенты, которые побывали и в театре, и в кино, и в цирке, и если есть, то сколько их.

42.В салоне небольшого самолета было 42 пассажира. Некоторые из них были москвичами, остальные – иногородними. Среди москвичей было 9 мужчин. Некоторые из пассажиров были артистами, но ни одна из иногородних женщин артисткой не была. Всего иногородних мужчин было 18. Из них 13 не были артистами. Среди пассажиров, не являвшихся артистами, было 16 мужчин и 11 женщин. 5 москвичей не были артистами. Сколько всего артистов было в самолете?

43.При досмотре на таможне с поезда были сняты несколько коробок, среди которых были коробки картонные и деревянные. Эти коробки были только двух размеров: большие и маленькие, причем одни из них были покрашены в зеленый цвет, а другие – в черный. Оказалось, что было задержано 16 зеленых коробок, причем зеленых коробок большого размера – 6, а больших зеленых коробок из картона – 4. Черных коробок из картона было 8, а черных коробок из дерева – 9. Больших деревянных коробок было 7, а маленьких деревянных коробок было 11. Выясните, сколько коробок было снято с поезда и сколько среди них маленьких.

44.При обследовании читательских вкусов студентов оказалось, что: 60% студентов читает журнал A; 50% – журнал B; 50% – журнал C; 30% – журналы A и B; 20% – журналы B и C; 30% – журналы A и C; 10% – все три журнала.

1) Сколько процентов студентов читает ровно два журнала? 2) Сколько процентов студентов не читает ни один журнал?

45.Относительно группы в 30 студентов известно, что: 19 студентов изучают математику; 17 – музыку; 11 – историю; 12 – математику и музыку; 7 – историю и математику; 5 – музыку и историю; 2 – математику, историю и музыку.

1) Сколько студентов изучает ровно два предмета из трех? 2) Сколько студентов изучают математику, но не изучают историю? 3) Имеются ли в группе студенты, которые не изучают ни один из указанных предметов?

46.В результате проверки из 36 сотрудников фирмы только двое не были заподозрены ни во взяточничестве, ни в сокрытии налогов, ни в злоупотреблениях служебным положением. Обвинение во взяточничестве было предъявлено 11 сотрудникам, в сокрытии налогов – 25, а в злоупотреблении служебным положением – 17. При этом во взяточничестве и сокрытии налогов – 6, во взяточничестве и в злоупотреблении служебным положением – 10, в сокрытии налогов и злоупотреблении служебным положением – 4. Определить, есть ли сотрудники, которые имеют отношение ко всем трем нарушениям.

47. В трансконтинентальном самолетенаходятся: 9 мальчиков, 5 американских детей, 9 взрослых мужчин, 7 иностранных мальчиков, 14 американцев, 6 американцев мужского пола и 7 иностранок женского пола. Сколько людей в самолете? (Иностранцами считаются люди, которые не являются американцами).

48.Исследование показало, что среди 100 коллекционеров, 63 человека собирают картины, 59 – марки и 38 – открытки. Известно также, что 44 человека собирают картины и марки, 25 – картины и открытки, 20 – марки и открытки. Кроме того, 13 человек коллекционируют и картины, и марки, и открытки.

1) Есть ли среди обследуемых мнимые коллекционеры? 2) Сколько человек коллекционируют только один из трех предметов? 3) Сколько человек коллекционируют ровно два из трех предметов?