Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 66 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

66
a
2
,...., a
4
’) – количество предметов, обладающих свойством a
1
, a
2
, но не об-
ладающих свойством a
4
’.
В самом простом случае при одном свойстве
N(a’) = N – N(a),
где N общее число элементов, формула очевидна.
Если имеются два свойства a
1
, a
2
, то N(a
1
’,a
2
’) = N – N(a
1
) –– N(a
2
) +
N(a
1
, a
2
).
Действительно, каждый элемент, обладающий свойствами a
1
и a
2
од-
новременно вычитается дважды, следовательно, к этой разности нужно до-
бавить N(a
1
, a
2
) .
Обобщением этого правила является принцип включения–
исключения:
N(a
1
’, a
2
’, ..., a
n
’) = N – N(a
1
) – N(a
2
) – ..... – N(a
n
) + + N(a
1
a
2
) + N(a
1
a
3
) +
..... + N(a
n–1
a
n
) – N(a
1
a
2
a
3
) –
N(a
1
a
2
a
4
) – ....– N(a
n-2
a
n-1
a
n
) + ... +(–1)
n
N(a
1
a
2
....a
n
).
Задача 1. Сколько чисел в первой сотне, которые не делятся нацело
ни на 2, ни на 3, ни на 5?
Эта задача решается с помощью формулы включения–исключения.
Введем следующие обозначения:
-
a
1
– свойство чисел делиться на 2;
-
a
2
– свойство чисел делиться на 3;
-
a
3
– свойства чисел делиться на 5.
Следовательно,
-
a
1
a
2
означает, что число делится на 6;
-
a
1
a
3
означает, что число делится на 10;
- a
2
a
3
означает, что число делится на 15;
-
a
1
a
2
a
3
означает, что число делится на 30.
По формуле включения–исключения имеем
N(a
1
’a
2
’a
3
’) = 100 – N(a
1
) – N(a
2
) – N(a
3
) + N(a
1
a
2
) +
+ N(a
1
a
3
) + N(a
2
a
3
) – N(a
1
a
2
a
3
);
N(a
1
) = 50; N(a
2
) = 33; N(a
3
) = 20; N(a
1
a
2
) = 16;
N(a
1
a
3
) = 10; N(a
2
a
3
) = 6; N(a
1
a
2
a
3
) = 3.
N(a
1
’a
2
’a
3
’) =100 –50 – 33 – 20 + 16 + 10 + 6 – 3 = 26.
Таким образом, 26 чисел из100 не делятся ни на 2, ни на 3, ни на 5.
Аналогичная задача 2. Сколько чисел не делятся нацело на 2, 3, 5, из
первой тысячи? Эти задачи в математике были сформулированы математи-
a2,...., a4’) – количество предметов, обладающих свойством a1, a2 , но не об-
ладающих свойством a4’.
         В самом простом случае при одном свойстве
                                           N(a’) = N – N(a),
где N общее число элементов, формула очевидна.
         Если имеются два свойства a1, a2, то N(a1’,a2’) = N – N(a1) –– N(a2) +
N(a1, a2).
         Действительно, каждый элемент, обладающий свойствами a1 и a2 од-
новременно вычитается дважды, следовательно, к этой разности нужно до-
бавить N(a1, a2) .
         Обобщением этого правила является принцип включения–
исключения:
         N(a1’, a2’, ..., an’) = N – N(a1) – N(a2) – ..... – N(an) + + N(a1a2) + N(a1a3) +
                                 ..... + N(an–1an) – N(a1a2a3) –
                  N(a1a2a4) – ....– N(an-2an-1an) + ... +(–1)n N(a1a2....an).
         Задача 1. Сколько чисел в первой сотне, которые не делятся нацело
ни на 2, ни на 3, ни на 5?
         Эта задача решается с помощью формулы включения–исключения.
         Введем следующие обозначения:
         - a1 – свойство чисел делиться на 2;
         - a2 – свойство чисел делиться на 3;
         - a3 – свойства чисел делиться на 5.
         Следовательно,
         - a1a2 означает, что число делится на 6;
         - a1a3 означает, что число делится на 10;
         - a2a3 означает, что число делится на 15;
         - a1a2a3 означает, что число делится на 30.
         По формуле включения–исключения имеем
                     N(a1’a2’a3’) = 100 – N(a1) – N(a2) – N(a3) + N(a1a2) +
                               + N(a1a3) + N(a2a3) – N(a1a2a3);
                         N(a1) = 50; N(a2) = 33; N(a3) = 20; N(a1a2) = 16;
                              N(a1a3) = 10; N(a2a3) = 6; N(a1a2a3) = 3.
         N(a1’a2’a3’) =100 –50 – 33 – 20 + 16 + 10 + 6 – 3 = 26.
         Таким образом, 26 чисел из100 не делятся ни на 2, ни на 3, ни на 5.
         Аналогичная задача 2. Сколько чисел не делятся нацело на 2, 3, 5, из
первой тысячи? Эти задачи в математике были сформулированы математи-


                                          66

Страницы