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

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

Задача 1. В классе 30 учащихся, 16 из них занимаются музыкой, 17 увлекаются теннисом, а 10 занимаются и музыкой, и теннисом. Есть ли в классе ученики, равнодушные и к музыке, и к теннису, и если есть, то сколько их?

Решение. Если сложить число учащихся, интересующихся музыкой, с числом учащихся, занимающихся теннисом, т. е. 16 + 17 = 33, то учащиеся, интересующиеся и музыкой, и теннисом, окажутся учтенными дважды. Поэтому, чтобы определить число учащихся, интересующихся музыкой или теннисом, нужно из суммы 16 + 17 вычесть число учащихся, учтенных дважды, т. е. тех, кто интересуется и музыкой, и теннисом. По условию их 10. Таким образом, число интересующихся теннисом или музыкой равно: 16 + 17 – 10 = 23 ученика. А так как в классе всего 30 учащихся, то 30 – 23 = 7 учащихся равнодушны и к музыке, и к теннису.

Задача 1 решена по следующему алгоритму. Пусть имеется два конечных множества А и В. Тогда п(А) – число элементов в множестве А, п(В) – число элементов в множестве В,

п(А È В) = п(А) + п(В) – п(А Ç В). (1)

В нашем случае А — множество учащихся, интересующихся музыкой, и п(А) =16, В — множество учащихся, интересующихся теннисом, и п(В)=17, п(АÇ В) = 10, и тогда по формуле (1) п(А È В) = 16 + 17 – 10 = 23.

Усложним задачу: пусть к тем, кто интересуется в классе музыкой — множеству А, и к тем, кто увлекается теннисом — множеству В, добавляются еще и те, кто интересуется театром — множество С. Сколько учеников увлекается или музыкой, или теннисом, или театром, т. е. чему равно число п(АÈ В È С)?

Если множества А, В и С пересекаются лишь попарно, т. е. А Ç В Ç С = Æ, то подсчет можно вести, как и прежде: сначала сложить п(А) +п (В) + п(С), а затем вычесть число тех элементов, которые подсчитаны дважды, т. е. вычесть число n(A Ç B) + n(A Ç C) + n(B Ç C).

Если же множество А Ç В Ç С ¹ Æ, то его элементы оказались неучтенными: сначала их трижды учли, когда складывали п(А) +п(В) + п(С), а затем трижды отнимали их, вычитая n (A Ç B) + n(A Ç C) + n(B Ç C). Таким образом, число

п(А) + п(В) + п(С) – n (A Ç B) + n(A Ç C) + n(B Ç C)

меньше истинного результата ровно на число элементов в пересечении множеств

А Ç В Ç С, которое и следует добавить для получения верного результата:

п(А È В È С) = п(А) + п(В) + п(С) – n (A Ç B) + n(A Ç C) + n(B Ç C) +

+ n (A Ç B Ç C) (2)

Аналогичная формула может быть получена для любого числа множеств.

В формулах (1) и (2) подсчитывается, сколько раз каждый элемент включается и исключается, поэтому их называют формулами включений и исключений.

Задача 2. На вступительном экзамене по математике были предложены три задачи: по алгебре, планиметрии и стереометрии. Из 1000 абитуриентов задачу по алгебре решили 800, по планиметрии — 700, а по стереометрии — 600 абитуриентов. При этом задачи по алгебре и планиметрии решили 600 абитуриентов, по алгебре и стереометрии — 500, по планиметрии и стереометрии — 400. Все три задачи решили 300 абитуриентов. Существуют ли абитуриенты, не решившие ни одной задачи, и если да, то сколько их?

Решение. Пусть U — множество всех абитуриентов, А — множество абитуриентов, решивших задачу по алгебре, В — множество абитуриентов, решивших задачу по планиметрии, С — множество абитуриентов, решивших задачу по стереометрии.

По условию п(U) = 1000, п(А) п(В) = 800, п(В) = 700, п (С) = 600, n (A Ç B) = 600, n(A Ç C) = 500, n(B Ç C )= 400, п (АÇ ВÇ С) = 300.

В множество АÈ ВÈ С включены все абитуриенты, решившие хотя бы одну задачу. По формуле (2) имеем:

п (А È BÈ C) = 800 + 700 + 600 – 600 – 500 – 400 + 300 = 900.

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

п(U) — п(А È BÈ C)= 1000 – 900 = 100 (абитуриентов).

Решение задач подобного вида хорошо иллюстрируется на кругах Эйлера.