НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

предыдущая главасодержаниеследующая глава

Включение и исключение

Известна старинная шутка о том, что лошадь имеет не меньше 12 ног: две спереди, две сзади, по две с каждого бока, по одной "с каждого угла" - и это не считая ног, которые снизу!

Аналогичный "парадокс" связан с доказательством того, что в течение года человек не успевает работать. Действительно, из 365 дней в году 104 падают на субботние и воскресные дни, 7 - на праздники, 10 - на отпуск*. Далее, 1/3 времени, то есть 122 дня, уходит на сон, а другая треть, то есть еще 122 дня, лежит за пределами восьмичасового рабочего дня. Итак, 104 + 7 + 10 + 122 + 122 = 365 дней в году, не занятых работой!

* (Здесь автор исходит из данных, относящихся к его стране; читатель может, разумеется, перевести их на наши условия - при этом окажется, что свободного времени в году у него свыше 365 дней!)

Очевидно, что "изюминка" рассмотренных выводов заключается в наличии пересечений различных групп, которые мы подсчитывали как якобы независимые. Так, спереди и с правого бока у лошади есть общая нога, а все "угловые" ноги одновременно находятся и снизу. Подобным же образом, часть восьмичасовых отрезков времени, отводимых для сна, приходится на выходные и праздничные дни; поэтому в приведенном выше решении они считались дважды. Существует весьма простая формула, дающая точный ответ на любую задачу подобного типа и учитывающая все пересечения суммируемых групп. Она носит название "формула включений и исключений" (иногда ее называют также формулой перекрестной классификации).

Теорема 6. Пусть задано множество, содержащее N элементов, причем N1 из них обладают свойством Р1, N2 - свойством Р2 и так далее, наконец, Nr обладают свойством Рr. Тогда число элементов, которые не обладают ни одним из свойств Р1, Р2, ..., Рr (обозначим это число через N0) равно

N0 = N - (N1 + N2 + ... + Nr) + (N1,2 + N1,3 + ... + N2,3 + ... N(r-1),r) - (N1,2,3 + N1,2,4 + ... + N(r-2),(r-1),r) +- ... ± (N1,2,3...r),

где через Ni,j...m обозначено число элементов, обладающих одновременно свойствами Рi, Рj, ... , Рm.

Пример. Возьмем N = 365, а через P1 обозначим свойство дня быть выходным, Р2 - праздником, Р3 - днем отпуска, через Р4 - свойство быть временем, потраченным на сон, и через Р5 - нерабочее время, в течение которого человек бодрствует. Тогда N1 = 104 дня, N2 = 7 дней, N3 = 10 дней, N4 = N5 = 122 дня. При этом N1,4 = 104:3 = 342/3 дня; N2,4 = 7:3 = 21/3 дня; N3,4 = 10:3 = 31/3 дня; N1,5 = 104:3 = 342/3 дня; N2,5 = 7:3 = 21/3 дня и, наконец, N3,5 = 10:3 = 31/3 дня. Остальные Ni,j, ..., m = 0. Следовательно, N0 (рабочее время) равно N0 = N - (N1 + N2 + N3 + N4 + N5) + (N1,4 + N2,4 + N3,4 + N1,5 + N2,5 + N3,5) = 365 - 365 + 242/3 = 802/3 дня = 1936 ч = 48,4 сорокачасовой рабочей недели.

Доказательство. Из исходного множества в N элементов мы вычитаем N1 элементов, обладающих свойством Р1, N2 элементов, обладающих свойством Р2, и т. д. Однако каждый элемент, обладающий двумя из этих свойств, вычитался дважды. Поэтому эти элементы следует восстановить, для чего необходимо добавить члены Ni,j. Далее, элементы, обладающие тремя из данных свойств - например, свойствами Рi, Pj и Pk, - трижды вычитались (рассмотрите выражение - Ni - Nj - Nk) и трижды восстанавливались (рассмотрите сумму Ni,j + Ni,k + Nj,k). Поэтому их следует вычесть из N, что мы и делаем, добавляя члены - Ni,j,k. В общем случае элемент, обладающий t из наших r свойств, вычитался t раз, затем добавлялся (2t) раз, снова вычитался (3t) раз, добавлялся (4t) раз и т. д. В результате он был добавлен к N ровно - t + (2t) - (3t) + - ... ± (tt) раз. Это выражение на 1 меньше, чем 1 - (1t) + (2t) - (3t) + - ... ± (tt) = 0 (ср. свойство 2 биномиальных коэффициентов на стр. 90). Поэтому в итоге любой элемент, обладающий хотя бы одним из r указанных свойств, был вычтен из N ровно один раз*.

* (Более краткое (но также требующее известного внимания) доказательство формулы включений и исключений базируется на принципе математической индукции (ср. выше, стр. 19); оно приведено, например, в книге Н. Я. Виленкина, стр. 26-27 (см. сноску на стр. 80).)

Примеры

1. Рыбак собирается ловить рыбу на площади 1000×1500 миль (рис. 91). Однако ему запрещено заходить в районы A, В и С, представляющие собой квадраты со сторонами 500 миль, центры которых удалены один от другого на 400 миль. На какой площади может он ловить рыбу?

Рис. 91. Задача рыбака
Рис. 91. Задача рыбака

Площадь ловли рыбы F получится из площади всего района Т вычитанием площадей А, В, С, затем добавлением площадей, принадлежащих одновременно А и В, А и С, В и С (каждая из них содержит площадь, принадлежащую всем трем районам), и, наконец, вычитанием общей площади трех районов А, В и С. Нахождение численного ответа оставляем читателю в качестве упражнения.

2. Пусть число n имеет различные простые делители р1, р2, ..., рr. Сколько чисел от 1 до n взаимно просты с n (то есть не имеют с n общих простых делителей)?

Соответствующее число обозначается φ(n); эта функция от n называется функцией Эйлера. (По разным соображениям число 1 не рассматривается как простое. Если бы мы считали 1 простым числом, то для любого числа, меньшего п, нашелся бы общий с n простой делитель; поэтому для всех n мы имели бы φ(n) = 0.) Поэтому φ(1) = 1; φ(2) = 1; φ(3) = 2; φ(4) = 2; φ(5) = 4; φ(6) = 2; φ(7) = 6; φ(8) = 4 и т. д.

Обозначим через Р1 свойство делиться на р1, через Р2 - свойство делиться на р2, ..., через Рr - свойство делиться на рr. Тогда, по теореме 6,

φ(n) = n - (n1 - n2 + ... + (nr) + (n1,2 + n1,3 + ...) - (n1,2,3 + ...) ± ... = n - (n/p1 + n/p2 + ... + n/pr) + (n/p1p2 + n/p1p3 + ... + n/pr-1pr) - (n/p1p2p3 + n/p1p2p4 + ...) +- ... ± n/p1p2...pr = n(1 - 1/p1)(1 - 1/p2) ... (1 - 1/pr).
Упражнения

13. Для каждого значения n от 1 до 15 выпишите числа, меньшие n и не имеющие с ним общих делителей. (Простые числа в промежутке от 1 до 15 суть 2, 3, 5, 7, 11, 13.) Сравните полученные вами списки с ответами, найденными из только что выведенной формулы

φ(n) = n(1 - 1/p1)(1 - 1/p2) ... (1 - 1/pr).

14. Пусть p1, p2, ..., pm - простые числа, не превосходящие √x. Покажите, что число простых чисел, не превосходящих х (обозначаемое через π(х)), задается выражением

π(x) = m - 1 + [x] - ([x/p1] + [x/p2] + ... + [x/pm]) + ([x/p1p2] + [x/p1p3] + ... + [x/pm-1pm]) - ... ± [x/p1p2 ... pm],

где через [x/p] обозначена так называемая целая часть дроби x/n, т. е. наибольшее целое число, не превосходящее x/p. (Указание: а) Если число между 1 и х - составное, то хотя бы один из его простых делителей будет меньше √x. Почему? б) Число кратных р чисел, не превосходящих x, равно [x/p]. Почему? в) Не забудьте включить в π(х) первые m простых чисел и исключить единицу, которая не является простым числом.)

15. Простые числа, не превосходящие √100, суть 2, 3, 5 и 7. Используйте формулу предыдущей задачи для нахождения π(100). Совпадает ли ответ с непосредственно подсчитанным числом простых чисел от 1 до 100?

16. Среди 50 бездомных собак 12 болеют чумкой, у 18 - блохи, у 11 - глисты и шесть собак бешеные. Кроме того, у пяти из них чумка и блохи; у трех собак - блохи и бешенство, у четырех - чумка и глисты, у пяти - блохи и глисты, а у двух - чумка, блохи и глисты одновременно. Предполагая, что эти собаки больше ничем не болеют и среди них нет собак, больных другими комбинациями болезней, определите, сколько среди этих 50 собак здоровых?

предыдущая главасодержаниеследующая глава











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru