ТГиК-2019-Семинар-14.10.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

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

$$|A\bigcup B| = |A| + |B| - |A\bigcap B|$$

$$|\bigcup_{i=1}^n A_i| = \sum_i^n |A_i| - \sum_{i<j}^n |A_i \bigcap A_j| + \sum_{i<j<k}^n |A_i \bigcap A_j \bigcap A_k| - ... - (-1)^{n-1} |A_1 \bigcap A_2 \bigcap ... \bigcap A_n|$$

Для n = 3:

$$|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| $$

Задачи на семинар и самостоятельную работу

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

Решение:

A = { x| x ⋮ 2}

B = { y| y ⋮ 3}

|A ∪ B| = |A| + |B| - |A∩B|

|A ∪ B| = 50 + 33 - 16 = 67

Ответ: 67

2.Даны числа от 1 до 4, i1 ,i2 ,i3 ,i4 такие что ij = j

Найти Ai - множество перестановок, в котором i на i -тых местах. |Ai| = 3! = 6

Решение:

$$|A_1∪A_2∪A_3∪A_4|=B_1 - B_2 + B_3 - B_4 = 26$$

$$B_1 = 24$$

$$B_2 = 2C_4^2$$

$$B_3 = 1!C_4^3$$

$$B_4 = 0!C_4^4$$

$$|\bigcup_{i=1}^n A_i| = \sum_{i=1}^n (-1)^{i+1}(n - i)!C_n^i = \sum_{i=1}^n (-1)^{i+1} \frac{n!}{i!}$$

3.Кость бросают 8 раз. Найти вероятность, что ни одна цифра не встретится больше одного раза. |Ai| = $$(\frac{5}{6})^8$$

$$|A_i \bigcup A_j| = (\frac{4}{6})^8$$

$$|\bigcup_{i=1}^6 A_i| = \frac{5^8 - 4^8 + 3^8 - 2^8 +1}{6^8}$$

3.Даны n человек, из них 6 говорят по-английски, 7 по-французски, 6 по-немецки, 4 по-английски и по-немецки, 3 по-немецки и по-французски, 2 по-французски и по-английски, 1 на всех трех языках.

1)Чему равно n?

2)Сколько человек знают только английский?

3)Сколько человек знают только один язык?

4)Сколько человек знают только французский?

Решение:

1) $$|A_1∪A_2∪A_3| = |A_1| + |A_2| + |A_3| - |A_1 ∩ A_2| - |A_2 ∩ A_3| - |A_1 ∩ A_3| + |A_1 ∩ A_2 ∩ A_3| = 6 + 7 + 6 - 2 - 4 - 3 - 1 = 11$$

2) $$|A_0| = 6 - 4 - 2 + 1 = 1$$

3) $$|N| = 4$$

4) $$|F_0| = 7 - 3 - 2 + 1 = 3 $$

4.Из 92 человек, 48 имеют бутерброды с колбасой, 38 с сыром, 42 с ветчиной, 28 с сыром и с колбасой, 26 с сыром и ветчиной, 31 с колбасой и ветчиной, с тремя ингредиентами 25.

Сколько человек не имеют бутербродов?

Решение:

$$|\bigcup A| = 48 + 38 + 42 - 28 - 31 - 26 + 25 = 68$$

92 - 68 = 24

Ответ: 24

5.Сколько существует целых чисел от 1 до 1000000, которые не являются ни полным квадратом, ни полным кубом, ни четвёртой степенью?

Решение:

1000000 = 1000² = 100³ = 106.  Поэтому в указанном промежутке ровно 1000 квадратов и 100 кубов. 10 чисел из них являются шестыми степенями, то есть квадратами и кубами одновременно. Все четвёртые степени находятся среди квадратов. Следовательно, условию удовлетворяют

$$|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| = 1000 + 100 - 10$$

1000000 – 1000 – 100 + 10 = 998910  чисел.

6.Сколькими способами можно расселить 15 гостей в четырёх комнатах, если требуется, чтобы ни одна из комнат не осталась пустой?

Решение:

Без указанного ограничения есть 415 способов. В 315 из них первая (вторая, третья, четвертая) комната будет пуста. В 215 способов будет пуста фиксированная пара комнат, и по одному способу, когда три фиксированные комнаты будут пусты. По формуле включения-исключения имеется  415 – 4·315 + 6·215 – 4  способа, когда все комнаты непусты.

415 – 4·315 + 6·215 – 4  способа.

Ответ: 4