No Image

Формула включений и исключений для четырех множеств

СОДЕРЖАНИЕ
5 просмотров
11 марта 2020

На этой странице мы собрали примеры решения учебных задач на применение принципа включений-исключений в комбинаторных задачах по теории вероятностей или дискретной математике.

Краткая теория

Формула включений и исключений для двух множеств

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

В сумме $|A|+|B|$ пересечение $Acap B$ учтено дважды, поэтому для компенсации мы вычитаем $|Acap B|$.

Формула включений и исключений для трех множеств

Для любых конечных множеств $A$, $B$ и $C$ справедливо равенство:

$$ | A cup B cup C | =|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap B cap C|. $$

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

Разберем примеры решений типовых задач с этой формулой включений и исключений для случая 2 и 3 множеств (другие примеры подобных заданий вы найдете в разделе Примеры по дискретной математике: Множества и отношения).

Примеры решенных задач

Задача 1. Формула включений и исключений (для трех множеств). Известно, что свойством А обладает n объектов, В — m объектов, С — с объектов, АВ — р объектов, АС — g объектов, ВС — r объектов, АВС — q объектов. Сколько всего объектов?

Задача 2. Из 100 человек студентов, сдавших сессию, 48 человек сдали экономику, 42 студента – математику и 37 человек – логику. По экономике или математике сдали экзамен 76 человек, по экономике или логике также 76 человек, а по математике или логике – 66 человек. Сколько человек сдали хотя бы один экзамен, если все три предмета сдали 5 человек? Сколько человек не сдали ни одного экзамена? Сколько человек сдали только один экзамен по логике?

Задача 3. При обследовании читательских вкусов студентов оказалось, что 60 % студентов читают журнал А, 50 % – журнал В, 50 % – журнал С, 30 % – журналы А и В, 20 % – журналы В и С, 40 % – журналы А и С, 10 % – журналы А, В и С. Выяснить, сколько процентов студентов:
1) не читает ни одного из журналов;
2) читает в точности два журнала;
3) читает не менее двух журналов.

Задача 4. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро – немецкий, шестеро – французский, пятеро знают английский и немецкий, четверо – английский и французский, трое – немецкий и французский. Выяснить:
1) сколько человек знают все три языка;
2) сколько человек знают ровно два языка;
3) сколько человек знают только английский язык.

Задача 5. Из 100 туристов, выехавших в заграничное путешествие, 10 человек не знают ни немецкого, ни французского языков, 76 человек знают немецкий и 83 – французский. Сколько туристов знают оба эти языка?

Задача 6. В отряде из 40 ребят 30 умеют плавать; 27 умеют играть в шахматы; 5 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.

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

Решебник по терверу и комбинаторике

Если решения нужны срочно и почти даром? Ищите в решебнике по теории вероятностей:

Пусть задано конечное множество А. Число его элементов обозначим n(А). Найдем сколько элементов содержится в множестве А ∪ В. Основная формула нахождения числа элементов суммы двух множеств

n(А ∪ В) = n(А) + n(В) – n(А ∩ В) (1)

Действительно, n(А ∪ В) — это сумма числа элементов множеств А и В, но при подсчете элементы, принадлежащие А ∩ В учитывались дважды. С помощью формулы (1) можно получить формулы для определения числа элементов суммы любого числа множеств. Например,

n(А ∪ В ∪ С) = n(А ∪ (В ∪ С)) = n(А) + n(В ∪ С) – n(А ∩ (В ∪ С)) =

Читайте также:  Почему не включается яндекс музыка

= n(А) + n(В) + n(С) – n(В ∩ С) – n((А ∩ В) ∪ (А ∩ С)) =

= n(А) + n(В) + n(С) – n(В ∩ С) – (n(А ∩ В) + n(А ∩ С) – n((А ∩ В) ∩ (А ∩ С))) =

=n(А) + n(В) + n(С) – n(В ∩ С) – n(А ∩ В) – n(А ∩ C) + n(А ∩ В ∩ С).

n(А ∪ В ∪ С) = n(А) + n(В) + n(С) – n(А ∩ В) – n(В ∩ С) – n(А ∩ C) + n(А ∩ В ∩ С) (2)

Формулы (1) и (2) называют формулами включений и исключений .

Примеры с подробным решением.

Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

Обозначим через А — множество школьников, знающих английский язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.

Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,

n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.

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

n(A ∪ N ∪ F) = n(A) + n(N) + n(F) =

= n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =

= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.

Следовательно, не знают ни одного иностранного языка:

100 – 80 = 20 школьников.

Эту же задачу можно решить с помощью диаграммы Эйлера–Венна (рис. 1).

Так как 3 языка знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7,

немецкий и французский — 8 – 3 = 5 школьников.

Только английский знают 42 –(2 + 3 + 7) = 30,

только немецкий — 30 – (2 + 3 + 5) = 20,

только французский — 28 – (3 + 5 + 7) = 13 школьников.

Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

Задача 2. Сколько двузначных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 11?

Решение. Обозначим: А — множество двузначных чисел, делящихся на 2;

В — множество двузначных чисел, делящихся на 3;

С — множество двузначных чисел, делящихся на 5;

D — множество двузначных чисел, делящихся на 11.

n(A ∪ B ∪ C ∪ D) — количество двузначных чисел, делящихся хотя бы на одно из чисел 2; 3; 5; 11.

n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) –

– n(A ∩ B) – n(A ∩ C) – n(A ∩ D) – n(B ∩ C) –

– n(B ∩ D) – n(C ∩ D) + n(A ∩ B ∩ C) + n(A ∩ B ∩ D) +

+ n(A ∩ C ∩ D) + n(B ∩ C ∩ D) – n(A ∩ B ∩ C ∩ D).

n(A) = 45, n(B) = 30, n(C) = 18, n(D) = 9,

n(A ∩ B) = 15, n(A ∩ C) = 9, n(A ∩ D) = 4, n(B ∩ C) = 6,

n(B ∩ D) = 3, n(C ∩ D) = 1, n(A ∩ B ∩ C) = 3,

n(A ∩ B ∩ D) = 1, n(A ∩ C ∩ D) = n(B ∩ C ∩ D) = n(A ∩ B ∩ C ∩ D) = 0.

Итак, n(A ∪ B ∪ C ∪ D) = 45 + 30 +18 + 9 – 15 – 9 – 4 – 6 – 3 – 1 + 3 + 1 = 68.

Так как всего 90 двузначных чисел, то чисел, не делящихся ни на одно из заданных чисел:

Задача 3. Известно, что из n учеников спортом увлекаются a учеников, программированием b, математикой c, спортом и программированием d, спортом и математикой e, программированием и математикой f , спортом, математикой и программированием g учеников. Сколько учеников увлекается только программированием? Сколько учеников увлекается только математикой? Сколько учеников ничем не увлекается?

Решение. Пусть A —множество учеников, которые увлекаются спортом,

B — программированием, С – математикой.

Тогда |A| = 32, |B| = 21, |C| = 23, |A ∩ B| = 8, |A ∩ C| = 12, |B ∩ C| =4 |A ∩ B ∩ C| = 3

Читайте также:  Зарядное устройство для джойстиков sony dualshock

|(A ∩ B) ∪ ( B ∩ C) | = |A ∩ B| + |B ∩ C| − |A ∩ B ∩ C| = 8 + 4 – 3 = 9

Тогда, только программированием занимается 21 – 9 = 12 учеников.

|(A ∩ C) ∪ ( B ∩ C) | = |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C| = 12 + 4 – 3 = 13

Тогда, только математикой занимается 23 – 13 = 10 учеников.

По формуле включений и исключений для трёх множеств находим число учеников увлекающихся спортом, программированием или математикой:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B∩ C| = =32+21+23-8-12-4+3 = 55

Значит, ничем не увлекается 70 − 55 = 15 человек. Ответ: 15.

1. В спортивном классе обучаются 24 человека. Каждый учащийся занимается хотя бы одним видом спорта (баскетболом или волейболом), из них баскетболом и волейболом занимаются 12 человек. Сколько человек занимается только волейболом, если их в 3 раза больше, чем тех, кто занимается только баскетболом?

2. В одном украинском городе все жители говорят на русском или украинском языке. По-украински говорят 80 % всех жителей, а по-русски — 75 %. Сколько процентов всех жителей говорят на обоих языках?

3. Группа ребят отправилась в поход. Семеро из них взяли с собой бутерброды, шестеро — фрукты, пятеро — печенье. Четве- ро ребят взяли с собой бутерброды и фрукты, трое — бутерброды и печенье, двое — фрукты и печенье, а один — и бутерброды, и фрукты, и печенье. Сколько ребят пошли в поход?

4. Староста класса, в котором 40 человек, подводил итоги по успеваемости группы за I полугодие. Получилась следующая картина: из 40 учащихся не имеют троек по русскому языку 25 человек, по математике — 28 человек, по русскому языку и мате- матике — 16 человек, по физике — 31 человек, по физике и ма- тематике — 22 человека, по физике и русскому языку 16 человек. Кроме того, 12 человек учатся без троек по всем трем предметам. Классный руководитель, просмотрев результаты, сказал: «В тво- их расчетах есть ошибка». Составьте диаграмму Эйлера–Венна и объясните, почему это так.

5. В лаборатории института работают несколько человек. Каждый из них знает хотя бы один иностранный язык. 7 человек знают английский, 7 — немецкий, 8 — французский, 5 знают английский и немецкий, 4 — немецкий и французский, 3 — французский и английский, 2 человека знают все три языка. Сколько человек работает в лаборатории? Сколько из них знает только французский язык? Сколько человек знает ровно 1 язык?

6. Сколько целых чисел от 0 до 999 не делятся ни на 5, ни на 7, ни на 11?

Ответы: 1. 9. 2. 55 %. 3. 10. 4. Если на диаграмме Эйлера– Венна отметить данные в непересекающихся множествах класса, то общее число учащихся класса получится равным 42, а не 40, как сказано в условии. 5. 12; 3; 4. 6. 376.

Пусть конечное множество А представлено как объединение некоторых конечных множеств Ах, . Ап, где А = = Ах и . и Ап. Как связаны количества элементов в множестве Лив множествах Аь . Ап? Для случая п = 2 на этот вопрос ответить легко.

Обозначим через т (Л) (мера множества Л) количество элементов в конечном множестве Л. Тогда:

так как общие элементы множеств Л! и Л2 включаются в объединение только один раз.

Пример 2.38. Из 220 школьников 163 умеют играть в хоккей, 175 — в футбол, 24 нс умеют играть в эти игры. Сколько школьников одновременно умеет играть в хоккей и футбол?

Решение. Введем обозначения: III — множество всех школьников, т(Ш) = 220; Ф — множество школьников, умеющих играть в футбол, /7?(Ф) = 175; X — множество школьников, умеющих играть в хоккей, т(Х) = 163; Ф n X — множество школьников, умеющих играть и в футбол, и в хоккей, Ф u X — множество школьников, умеющих играть хотя бы в одну из игр — или в футбол, или в хоккей. По у слови ю 24 школьника не умеют играть в эти игры, следовательно:

Читайте также:  Тигуан на вторичном рынке

Окончательно:

Ответ: 142 школьника играют и в футбол, и в хоккей.

Пример 2.39. Экзамен по математике сдавали 250 абитуриентов, оценку ниже 5 баллов получили 180 человек, а выдержали этот экзамен 210 абитуриентов. Сколько человек получили оценки 3 и 4?

Решение. Пусть А — множество абитуриентов, выдержавших экзамен; В — множество абитуриентов, получивших оценку ниже 5, по условию т(А) = 210, т(В) = 180, т <Аи В) = 250. Абитуриенты, получившие оценки 3 и 4, образуют множество А п В. Из формулы (2.2) находим:

Пример 2.40. В школе 1400 учеников. Из них 1250 умеют кататься на лыжах, 952 — на коньках. Ни на лыжах, ни на коньках не умеют кататься 60 учащихся. Сколько учащихся умеют кататься и на коньках, и на лыжах?

Решение. Множество учеников школы будем считать универсальным множеством U, А и В — соответственно множества учеников, умеющих кататься на лыжах и на коньках. Учащиеся, не умеющие кататься ни на лыжах, ни на коньках, составляют множество А’пВ’.

По условию т (Л’п В’) = 60, а так как Л’п5’=(Ли Б)'(пример 2.34, табл. 2.2), то и т(А и В)’ = 60. Отсюда

Зная т(А) и т(В), по формуле (2.2) находим:

Пример 2.41. На фирме работают 67 человек. Из них 47 знают английский язык, 35 — немецкий язык, а 23 — оба языка. Сколько человек в фирме нс знают ни английского, ни немецкого языков?

Решение. Решим эту задачу с помощью диаграмм Эйлера — Венна:

  • 12 + 23 + 24 = 59 человек знают хотя бы один из языков, следовательно,
  • 67 – 59 = 8 человек не знают ни одного из рассматриваемых языков (рис. 2.27).

Рис. 2.27. Решение задачи с помощью диаграмм Эйлера — Венна

Для подсчета числа элементов в объединении трех множеств (п = 3) (для общего случая их взаимного расположения)

Пример 2.42. В студенческой группе 25 человек. Во время летних каникул 9 из них выезжали в турпоездки за границу, 12 — путешествовали по России, 15 — отдыхали в Сочи, 6 — путешествовали за границей и по России, 7 — были и за границей, и в Сочи, 8 — и путешествовали по России, и были в Сочи и 3 — участвовали во всех трех поездках. Сколько студентов никуда не выезжало?

Решение. Пусть: Г — множество студентов, выезжавших за границу; Р — множество студентов, путешествовавших по России; С — множество студентов, отдыхавших в Сочи.

Тогда множество студентов, выезжавших хотя бы куда-то из города, есть Г u Р и С. Так как 9 + 12 +15 = 36 > 25, то множества Г, Р, С пересекаются (это видно и непосредственно из условия задачи, так как некоторые студенты были в различных поездках).

Имеем: т(Г) = 9; т( Р) = 12; т( С) = 15; m(t n Р) = 6; /и(Г пС) = 7; т(Р n С) = 8; m(Y n Р п С) = 3.

Тогда: тп(Г u Р и С) = 9 + 12 + 15 – 6 – 7 – 8 + 3 = 39 – 21 = 18, а из города никуда не выезжало 25 – 18 = 7 студентов.

Ответ. Никуда не выезжало 7 студентов.

Пример 2.43. В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих, 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 — защитниками и полузащитниками, шесть — нападающими и полузащитниками, а один и нападающим, и защитником, и полузащитником. Вратари незаменимы. Сколько в команде вратарей?

Решение. Используем метод с диаграммами Эйлера — Венна (рис. 2.28).

Рис. 2.28. Решение задачи с помощью диаграмм Эйлера — Венна

Один игрок может быть и нападающим, и защитником, и полузащитником, следовательно, два игрока (2 = 3- 1) могут быть только нападающими и защитниками и не могут быть полузащитниками. Девять игроков (9 = 10 – 1) могут быть защитниками и полузащитниками, но нс могут быть нападающими. Пять игроков (5 = 6- 1) могут быть нападающими и полузащитниками, но не могут быть защитниками и т.д.

В конечном итоге: 1 + 2 + 5 + 9+ 10 + 5 + (-4) = 28 игроков и 30 – 28 = 2 вратаря.

Комментировать
5 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector