Дискретная математика. Ерош И.Л - 69 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

69
Теорема.
Пусть имеется множество из N объектов произвольной природы и
пусть задано n произвольных свойств так, что объекты могут обладать
или не обладать некоторыми из этих свойств. Сами свойства обозна
чим a
1
, a
2
, …, a
n
. Кроме того, будем обозначать N(a
i
) – количество
объектов, точно обладающих свойством a
i
и, может быть, какимито
другими, а N(
i
1 ,
j
1
) – число объектов, не обладающих ни свойством
a
i
, ни свойством a
j
. Тогда число объектов, не обладающих ни одним из
перечисленных свойств, будет равно
N(
1
1
,
1
2
, …,
1
n
) = N – N(a
1
) – N(a
2
) – … N(a
n
) +
+N(a
1
, a
2
) + N(a
1
, a
3
) + … N(a
1
, a
n
) + N(a
2
, a
3
) +… N(a
n–1
, a
n
) –
– N(a
1
, a
2
, a
3
) – … N(a
1
, a
2
, a
3
, …, a
n
). (4.6)
Продолжим рассмотрение примера. Дополнительное тестирование
на предприятии показало, что 20 человек знают французский, 12 – ан
глийский и французский, 11 – немецкий и французский и 5 – все три
языка.
Тогда в соответствии с теоремой количество человек, не знающих
ни английского, ни немецкого, ни французского языков, равно
N = 67 – 48 – 35 – 20 + 27 + 12 + 11 – 5 = 9.
Задача “Решето Эратосфена”.
Выпишем все числа от 1 до N. Сколько чисел из них делятся на k
нацело? Очевидно, что [N/k], где [x] обозначает целую часть числа x.
Тогда легко подсчитать количество чисел, которые не делятся на кон
кретные числа k
1
, k
2
, …, k
s
.
Пример. Сколько чисел в диапазоне от 1 до 100 не делятся ни на 5,
ни на 7?
Воспользуемся теоремой о включениях и исключениях. Под первым
свойством числа будем понимать делимость на 5, под вторым – дели
мость на 7. Тогда количество чисел, которые не делятся ни на 5, ни на
7, будет равно: 100 – 20 – 14 + 2 = 68.
Упражнение.
1. В механической мастерской работают 12 человек, из них 6 чело
век имеют дипломы слесаря, 4 – дипломы оператора станков с ЧПУ,
7 человек – дипломы фрезеровщика, 3 человека владеют двумя из пе
речисленных дипломов и 2 человека – всеми тремя. Начальство реши
ло уволить работников, не имеющих дипломов хотя бы по одной из этих
специальностей. Имеется ли такая возможность?
2. Найти количество чисел, не делящихся на 3, 5 и 7, в диапазоне
от 200 до 500.

Страницы