Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Метод включения-исключения для решения задач на множества

Теоретические сведения

Метод включения-исключения применяется для оценки числа элементов множества, обладающего в точности р свойствами, либо не обладающего ни одним изр свойств.

Основная формула, по которой находят количество элементов в объединении двух множеств, вычисляется по диаграмме Эйлера— Венна, так как часть элементов принадлежат одновременно А и В и не могут учитываются дважды:

АиВ = А + В-АпВ. (1.7)

Для трех множеств А, В и С формула пересчета выглядит следующим образом:

А и В и С = А + В + С -AnB-- А п С - В п С + |Д п В п С. (1.8)

Обобщая, получаем формулу включения и исключения для N объектов со свойствами, которыми эти объекты могут обладать или не обладать.

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

Если Хх, Х2, Хп — некоторые множества и их мощность равна |^(|, Х2, ..., Х п, тогда мощность объединения этих множеств равна

|X| ^ Х2 и*... ^ Xп| = |А,[| + |АГ2| + .- . + |Xп| —

- {|*, 0*21 + 1*, п *з| +... +1*„_, о *„ 1} +

и

+ {j-^Ч f'' X2 x3 + ... + |^/г-2 ^ ^n-1 ^ ^C/j|} "I" ••• "I"

(1.9)

+ (-l)"“1^, nl2n...nlj.

Рассмотрим несколько задач.

Задачи

Задача 1.22. В аудитории находятся несколько программистов. Шестеро знают VISIAL BASIC, шестеро — РНР, семеро умеют программировать на JAVA. Четверо знают VISIAL BASIC и РНР, трое — VISIAL BASIC и JAVA, двое — РНР и JAVA. Один из них умеет программировать на всех языках. Сколько человек в аудитории? Сколько из них знают только VISIAL BASIC?

Решение.

По условию задачи каждый из присутствующих знает хотя бы один язык программирования.

Зададим: Ру в — свойство знать VISIAL BASIC; Рр свойство знать РНР; Pj — свойство знать JAVA.

Тогда количество программистов в аудитории п

п = п(РуВ) + п(Рр) + n(Pj) - n(PVB & Рр) - n(PVB & Pj) -

- п(Рр &Pj) + n{PVB &Pp& Pj) = 6 + 6 + 7- 4- 3- 2 + 1 = 11.

По формуле включений и исключений получается, что людей, знающих только VISIAL BASIC, нет:

п(РуВ, Рр-> Pj) — n(PVB) — н(РуВ & Рр) — n(PVB & Pj ) +

+ п(РуВ & Рр & Pj) = 6 — 4 — 3-1-1 = 0.

Задача 1.23. В комнате 15 человек. Из них 8 человек имеют темные глаза, 7 человек — темные волосы, 5 — темные волосы и темные глаза. Сколько из них темноволосых и светлоглазых людей?

Задача 1.24. В комнате 15 человек. Из них 8 человек имеют темные глаза, 7 человек — темные волосы, 5 — темные волосы и темные глаза. Сколько из них светловолосых и темноглазых людей?

Задача 1.25. В комнате 15 человек. Из них 8 человек имеют темные глаза, 7 человек — темные волосы, 5 — темные волосы и темные глаза. Сколько из них светловолосых и светлоглазых людей?

 
<<   СОДЕРЖАНИЕ   >>