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

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

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

1) Если А ₁ и А ₂ конечные множества и А ₁ ∩ А ₂ = Æ, то: m (A ₁ U A ₂) = m (A ₁) + m (A ₂) (1).

2) Если А ₁ и А ₂ конечные множества и А ₁ ∩ А ₂ ≠ Æ, то: m (A ₁ U A ₂) = m (A ₁) + m (A ₂) − m (A ₁ ∩ A ₂) (2), так как общие элементы множеств А ₁ и А ₂ включаются в объединение только один раз.

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

Решение. Введем обозначения: Ш – множество всех школьников, m (Ш) = 220, Ф – множество школьников, умеющих играть в футбол, m (Ф) = 175, Х – множество школьников, умеющих играть в хоккей, m (Х) = 163, Ф ∩ Х – множество школьников, умеющих играть и в футбол, и в хоккей, Ф U Х – множество школьников, умеющих играть хотя бы в одну из игр – или в футбол, или в хоккей. По условию 24 школьника не умеют играть в эти игры, следовательно:

m (Ф U Х) = m (Ш) – 24=196.

Окончательно: m (ФUХ) = m (Ф) + m (Х) – m (Ф ∩ Х), откуда m (Ф ∩ Х) = m (Ф) + m (Х) – m (Ф U Х) = 175 + 163 – 196 = 142.

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

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

Решение: Пусть А – множество абитуриентов, выдержавших экзамен, В – множество абитуриентов, получивших оценку ниже 5, по условию m (A)=210, m (В)=180, m (A UB)=250. Абитуриенты, получившие оценки 3 и 4, образуют множество А∩В. Из формулы (2) находим m (A∩B) = m (A) + m (В) - m (A UB) = 210 + 180 – 250 = 140.♦

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

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

m (А∩B) = m (А) + m (В) - m (А UB) = 862. ♦

По условию m (А’∩B’) = 60, а т.к. по формуле (3) А’∩B’=(А UВ)’, то и m (А UB)’= 60. Отсюда m (А UB) = m (U) - m (А UB)’=1340. Зная m (А) и m (В), по формуле (2) находим.

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

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

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

m (А U В U С) = m (А) + m (В) + m (С) - m (А∩В) – m (А∩С) –– m (В∩С) + m (А∩В∩С). (3)

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

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

Р – множество студентов, путешествовавших по России;

С – множество студентов, отдыхавших в Сочи.

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

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

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

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

1+2+5+9+10+5+(-4)=28, отсюда 30-28=2 вратаря.

Дата добавления: 2014-01-07