Теоретические основы принципа включений-исключений и особенности его применения в решениях задач по дискретной математике

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

Прежде чем приступать к изучению принципа включений и исключений, следует хорошо понимать, на чем основан этот принцип. А именно, один из основных разделов современной математики - множества.

Понятие множества является первичным, т. е. не поддается определению через другие, более простые понятия. С понятием множества мы встречаемся довольно часто: множество студентов нашего института, множество преподавателей, множество изучаемых дисциплин.

Хотя в силу первичности понятия множества нельзя дать ему строгое определение, но можно воспользоваться описательным определением, предложенным одним из создателей теории множеств - немецким математиком Георгом Кантором (1845-1918). Он сказал: «Множество есть многое, мыслимое нами как единое».

Все множества состоят из определенного конечного числа объектов, которые мы будем называть элементами множества. При этом каждый из объектов данного вида либо принадлежит, либо не принадлежит рассматриваемому множеству.

Множества, включающие только такие объекты, принадлежность или не принадлежность которых к тому или иному множеству не вызывает сомнения, называются четкими множествами. Поскольку каждый рассматриваемый объект либо принадлежит, либо не принадлежит к рассматриваемому четкому множеству, эти множества всегда имеют ясно очерченные границы. Четким множествам противопоставлены нечеткие или «лингвистические» множества, включающие такие объекты, которые могут быть отнесены к тому или иному множеству лишь с определенной степенью достоверности. Понятие нечетких множеств было впервые введено в 1965 году американским математиком Л. Заде.

Множества, которые состоят из конечного числа элементов, называются конечными множествами. К числу конечных множеств относится также и пустое множество, т.е. множество, не содержащее ни одного элемента. Введение понятия пустого множества связано с тем, что, определяя тем или иным способом множество, мы не можем знать заранее, содержит ли оно хотя бы один элемент. Например, множество отличников в какой-либо учебной группе.

Множества, рассматриваемые при решении практических задач, чаще всего имеет дело с конечными множествами объектов.

Не всякая задача комбинаторики решается непосредственным применением основных комбинаторных принципов -- правила суммы или произведения, подсчётом числа размещений или сочетаний. В некоторых случаях приходится идти окольным путем и действовать своеобразным «методом решета», который состоит в следующем: для нахождения числа элементов интересующего нас множества мы сначала находим число элементов некоторого большего множества, а потом «просеиваем» нужные элементы, постепенно отбрасывая лишние.

Принцип включений-исключений -- это важный комбинаторный приём, позволяющий подсчитывать размер каких-либо множеств, или вычислять вероятность сложных событий.

1. Теоретические основы принципа включений - исключений

1.1 Формулировки принципа включений-исключений. Доказательство принципа включений-исключений

Словесная формулировка.

Принцип включений-исключений выглядит следующим образом:

Чтобы посчитать размер объединения нескольких множеств, надо просуммировать размеры этих множеств по отдельности, затем вычесть размеры всех попарных пересечений этих множеств, прибавить обратно размеры пересечений всевозможных троек множеств, вычесть размеры пересечений четвёрок, и так далее, вплоть до пересечения всех множеств.

Формулировка в терминах множеств.

В математической форме приведённая выше словесная формулировка выглядит следующим образом:

Её можно записать более компактно, через сумму по подмножествам. Обозначим через множество, элементами которого являются . Тогда принцип включений-исключений принимает вид:

Эту формулу приписывают Муавру (Abraham de Moivre).

Формулировка с помощью диаграмм Венна.

Пусть на диаграмме отмечены три фигуры , и :

Рис. 1

Тогда площадь объединения равна сумме площадей А, В и С, за вычетом дважды покрытых площадей , , , но с прибавлением трижды покрытой площади :

.

Аналогичным образом это обобщается и на объединение фигур.

Формулировка в терминах теории вероятностей.

Если Ai (i=1…n) -- это события,P(Ai) -- их вероятности, то вероятность их объединения (т.е. того, что произойдёт хотя бы одно из этих событий) равна:

Эту сумму также можно записать в виде суммы по подмножествам множества , элементами которого являются события Ai

комбинаторный математический множество исключение

Доказательство принципа включений-исключений.

Для доказательства удобно пользоваться математической формулировкой в терминах теории множеств:

где , напомним, -- это множество, состоящее из Ai-ых.

Нам нужно доказать, что любой элемент, содержащийся хотя бы в одном из множеств Ai, учтётся формулой ровно один раз. (Заметим, что остальные элементы, не содержащиеся ни в одном из Ai, никак не могут быть учтены, поскольку отсутствуют в правой части формулы).

Рассмотрим произвольный элемент x, содержащийся ровно в множествах Ai. Покажем, что он посчитается формулой ровно один раз.

Заметим, что:

· в тех слагаемых, у которых size(C)=1 , элемент x учтётся ровно k раз, со знаком плюс;

· в тех слагаемых, у которых size(C)=2, элемент x учтётся (со знаком минус) ровно раз -- потому что x посчитается только в тех слагаемых, которые соответствуют двум множествам из k множеств, содержащих x;

· в тех слагаемых, у которых size(C)=3, элемент x учтётся ровно раз, со знаком плюс;

· в тех слагаемых, у которых size(C)=k, элемент x учтётся ровно раз, со знаком (-1)k-1;

· в тех слагаемых, у которых size(C)>k, элемент x учтётся ноль раз.

Таким образом, нам надо посчитать такую сумму биномиальных коэффициентов:

Проще всего посчитать эту сумму, сравнив её с разложением в бином Ньютона выражения (1-x)k:

Видно, что при x=1 выражение (1-x)k представляет собой не что иное, как 1-T. Следовательно, T=1-(1-1)k=1, что и требовалось доказать.

Принцип включений-исключений сложно хорошо понять без изучения примеров его применений.

Сначала мы рассмотрим три простые задачи "на бумажке", иллюстрирующие применение принципа, затем рассмотрим более практические задачи, которые трудно решить без использования принципа включений-исключений.

Особо следует отметить задачу "поиск числа путей", поскольку в ней демонстрируется, что принцип включений-исключений может иногда приводить к полиномиальным решениям, а не обязательно экспоненциальным.

1.2 Основные положения включений и исключений на примере решения задач

Простая задачка о перестановках

Сколько есть перестановок чисел от до таких, что первый элемент больше , а последний -- меньше 8?

Посчитаем число "плохих" перестановок, т.е. таких, у которых первый элемент и/или последний .

Обозначим через X множество перестановок, у которых первый элемент , а через Y -- у которых последний элемент . Тогда количество "плохих" перестановок по формуле включений-исключений равно:



Проведя несложные комбинаторные вычисления, получаем, что это равно:

Отнимая это число от общего числа перестановок , мы получим ответ.

Простая задачка о (0,1,2)-последовательностях

Сколько существует последовательностей длины , состоящих только из чисел 0, 1, 2, причём каждое число встречается хотя бы раз?

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

Обозначим через Ai.(i=0…2) множество последовательностей, в которых не встречается число i Тогда по формуле включений-исключений число "плохих" последовательностей равно:

Размеры каждого из Ai равны, очевидно, 2n (поскольку в таких последовательностях могут встречаться только два вида цифр). Мощности каждого попарного пересечения равны (поскольку остаётся доступной только одна цифра). Наконец, мощность пересечения всех трёх множеств равна (поскольку доступных цифр вообще не остаётся).

Вспоминая, что мы решали обратную задачу, получаем итоговый ответ:

Количество целочисленных решений уравнения

Дано уравнение:

x1+x2+x3+x4+x5+x6=20

где все (где ).

Требуется посчитать число решений этого уравнения.

Забудем сначала про ограничение , и просто посчитаем число неотрицательных решений этого уравнения. Это легко делается через биномиальные коэффициенты -- мы хотим разбить элементов на групп, т.е. распределить "стенок", разделяющих группы, по местам:

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

Аналогично, мощность пересечения двух множеств и равна числу:

Мощность каждого пересечения трёх и более множеств равна нулю, поскольку элементов не хватит на три и более переменных, больше либо равных .

Объединяя всё это в формулу включений-исключений и учитывая, что мы решали обратную задачу, окончательно получаем ответ:

Количество взаимно простых чисел в заданном отрезке

Пусть даны числа и . Требуется посчитать количество чисел в отрезке , взаимно простых с .

Сразу перейдём к обратной задаче -- посчитаем количество не взаимно простых чисел.

Рассмотрим все простые делители числа ; обозначим их через ().

Сколько чисел в отрезке , делящихся на ? Их количество равно:

Однако если мы просто просуммируем эти числа, то получим неправильный ответ -- некоторые числа будут просуммированы несколько раз (те, которые делятся сразу на несколько ). Поэтому надо воспользоваться формулой включений-исключений.

Например, можно за перебрать подмножество множества всех -ых, посчитать их произведение, и прибавить или вычесть в формуле включений-исключений очередное слагаемое.

Количество чисел в заданном отрезке, кратных хотя бы одному из заданных чисел:

Даны чисел и число . Требуется посчитать количество чисел в отрезке , которые кратны хотя бы одному из .

Алгоритм решения практически совпадает с предыдущей задачей -- делаем формулу включений-исключений над числами , т.е. каждое слагаемое в этой формуле -- это количество чисел, делящихся на заданный поднабор чисел (иными словами, делящихся на их наименьшее общее кратное).

Таким образом, решение сводится к тому, чтобы за перебрать поднабор чисел, за операций найти их наименьшее общее кратное, и прибавить или вычесть из ответа очередное значение.

Количество строк, удовлетворяющих заданному числу паттернов

Дано паттернов -- строк одинаковой длины, состоящих только из букв и знаков вопроса. Также дано число . Требуется посчитать количество строк, удовлетворяющих ровно паттернам либо, в другой постановке, как минимум паттернам.

Заметим вначале, что мы можем легко посчитать число строк, удовлетворяющих сразу всем указанным паттернам. Для этого надо просто "пересечь" эти паттерны: посмотреть на первый символ (во всех ли паттернах на первой позиции стоит вопрос, или не во всех -- тогда первый символ определён однозначно), на второй символ, и т.д.

Научимся теперь решать первый вариант задачи: когда искомые строки должны удовлетворять ровно паттернам.

Для этого переберём и зафиксируем конкретное подмножество паттернов размера -- теперь мы должны посчитать количество строк, удовлетворяющих этому набору паттернов и только ему. Для этого воспользуемся формулой включений-исключений: мы суммируем по всем надмножествам множества , и либо прибавляем к текущему ответу, либо отнимаем от него количество строк, подходящих под текущее множество:



где обозначает количество строк, подходящих под набор паттернов .

Если мы просуммируем по всем , то получим ответ:

Однако тем самым мы получили решение за время порядка .

Решение можно ускорить, заметив, что в разных суммирование зачастую ведётся по одним и тем же множествам .

Перевернём формулу включений-исключений и будем вести суммирование по . Тогда легко понять, что множество учтётся в формулах включений-исключений, везде с одним и тем же знаком :

Решение получилось с асимптотикой .

Перейдём теперь ко второму варианту задачи: когда искомые строки должны удовлетворять как минимум паттернам.

Понятно, мы можем просто воспользоваться решением первого варианта задачи и просуммировать ответы от до . Однако можно заметить, что все рассуждения по-прежнему будут верны, только в этом варианте задачи сумма по идёт не только по тем множествам, размер которых равен , а по всем множествам с размером .

Таким образом, в итоговой формуле перед будет стоять другой коэффициент: не один биномиальный коэффициент с каким-то знаком, а их сумма:

Количество путей.

Есть поле , некоторые клеток которого -- непроходимые стенки. На поле в клетке (левая нижняя клетка) изначально находится робот. Робот может двигаться только вправо или вверх, и в итоге он должен попасть в клетку , избежав все препятствия. Требуется посчитать число путей, которыми он может это сделать.

Предполагаем, что размеры и очень большие (скажем, до ), а количество -- небольшое (порядка ).

Для решения сразу в целях удобства отсортируем препятствия в том порядке, в каком мы можем их обойти: т.е., например, по координате , а при равенстве -- по координате .

Также сразу научимся решать задачу без препятствий: т.е. научимся считать число способов дойти от одной клетки до другой. Если по одной координате нам надо пройти клеток, а по другой -- клеток, то из несложной комбинаторики мы получаем такую формулу через биномиальные коэффициенты:

Теперь чтобы посчитать число способов дойти от одной клетки до другой, избежав всех препятствий, можно воспользоваться формулой включений-исключений: посчитаем число способов дойти, наступив хотя бы на одно препятствие.

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

Однако это снова будет неполиномиальное решение -- за асимптотику . Покажем, как получить полиномиальное решение.

Решать будем динамическим программированием: научимся вычислять числа -- число способов дойти от -ой точки до -ой, не наступив при этом ни на одно препятствие (кроме самих и , естественно). Всего у нас будет точки, поскольку к препятствиям добавляются стартовая и конечная клетки.

Если мы на секунду забудем про все препятствия и просто посчитаем число путей из клетки в клетку , то тем самым мы учтём некоторые "плохие" пути, проходящие через препятствия. Научимся считать количество этих "плохих" путей. Переберём первое из препятствий , на которое мы наступим, тогда количество путей будет равно , умноженному на число произвольных путей из в . Просуммировав это по всем , мы посчитаем количество "плохих" путей.

Таким образом, значение мы научились считать за время . Следовательно, решение всей задачи имеет асимптотику .

Число взаимно простых четвёрок.

Дано чисел: . Требуется посчитать количество способов выбрать из них четыре числа так, что их совокупный наибольший общий делитель равен единице.

Будем решать обратную задачу -- посчитаем число "плохих" четвёрок, т.е. таких четвёрок, в которых все числа делятся на число .

Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на делитель (но, возможно, делящихся и на больший делитель):



где -- это количество простых в факторизации числа , -- количество четвёрок, делящихся на .

Чтобы посчитать функцию , надо просто посчитать количество чисел, кратных , и биномиальным коэффициентом посчитать число способов выбрать из них четвёрку.

Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д.

Число гармонических троек.

Дано число . Требуется посчитать число таких троек чисел , что они являются гармоническими тройками, т.е.:

· либо,

· либо,

Во-первых, сразу перейдём к обратной задаче -- т.е. посчитаем число негармонических троек.

Во-вторых, заметим, что в любой негармонической тройке ровно два её числа находятся в такой ситуации, что это число взаимно просто с одним числом тройки и не взаимно просто с другим числом тройки.

Таким образом, количество негармонических троек равно сумме по всем числам от до произведений количества взаимно простых с текущим числом чисел на количество не взаимно простых чисел.

Теперь всё, что нам осталось для решения задачи -- это научиться считать для каждого числа в отрезке количество чисел, взаимно простых (или не взаимно простых) с ним. Хотя эта задача уже рассматривалась нами выше, описанное выше решение не подходит здесь -- оно потребует факторизации каждого из чисел от до , и затем перебора всевозможных произведений простых чисел из факторизации.

Число перестановок без неподвижных точек

Докажем, что число перестановок длины без неподвижных точек равно следующему числу:

и приблизительно равно числу:

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

Обозначим через множество перестановок длины с неподвижной точкой в позиции ().

Воспользуемся теперь формулой включений-исключений, чтобы посчитать число перестановок хотя бы с одной неподвижной точкой. Для этого нам надо научиться считать размеры множеств-пересечений , они выглядят следующим образом:

поскольку если мы знаем, что число неподвижных точек равно , то тем самым мы знаем позицию элементов перестановки, а все остальные элементов могут стоять где угодно.

Подставляя это в формулу включений-исключений и учитывая, что число способов выбрать подмножество размера из -элементного множества равно , получаем формулу для числа перестановок хотя бы с одной неподвижной точкой:

Тогда число перестановок без неподвижных точек равно:

Упрощая это выражение, получаем точное и приблизительное выражения для количества перестановок без неподвижных точек:

(поскольку сумма в скобках -- это первые членов разложения в ряд Тейлора )

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

1.3 Число элементов объединения и разности двух конечных множеств

Пусть A и B -- конечные множества. Число элементов множества A условимся обозначать символом m(A) и называть численностью множества A.

Определим численность объединения множеств A и B.

Если множества A и B не пересекаются то m(AB) = m(A) + m(B). Таким образом, численность объединения конечных непересекающихся множеств равна сумме численностей этих множеств.

Если множества A и B пересекаются, то в сумме m(A) + m(B) число элементов пересечения AB содержится дважды: один раз в m(A), а другой -- в m(B). Поэтому, чтобы найти численность объединения m(AB) , нужно из указанной суммы вычесть m(AB). Таким образом:

m(AB) = m(A) + m(B) - m(AB)

Определим теперь численность разности множеств A и B.

Если множества A и B не пересекаются то A \ B = A, и поэтому m(A\B) = m(A).

Если множества A и B пересекаются, то m(A\B) = m(A) - m(AB).

Если В А, то AB = B, и, следовательно, m(A\B) = m(A) - m(B).

Нам известно, как находят объединение двух конечных непересекающихся множеств. Например, если А = {х, у, z}, а В = {k,l,m,p}, то А?В ={х, у,z,k,l,m,p}. Чтобы ответить на вопрос: «Сколько элементов в полученном множестве?», достаточно пересчитать их.

А как определить число элементов в объединении конечных множеств, не образуя его и не обращаясь к пересчету элементов?

Условимся предложение «Множество А содержит а элементов» записывать в таком виде: n(А) = а. Например, если А = {х, у, z}, то утверждение «Множество А содержит три элемента можно записать так: n(А) = 3.

Можно доказать, что в множестве А содержится а элементов, а в множестве В - b элементов и множества А и В не пересекаются, то в объединении множеств А и В содержится а +b элементов, т.е.

n(А?В) = n(А) + n(В) = в + b. (1)

Это правило нахождения числа элементов в объединении двух конечных непересекающихся множеств, его можно обобщить на случай t попарно непересекающихся множеств, т.е. если множества А?, А?, …, А t попарно не пересекаются, то n(А? ? А? ? …? Аt) =n(А?) + n(А?) + … + n(Аt).

Для выше описанных множеств n(А) = 3,n(В) = 4. Видим, что А? В =?. Тогда n(А?В) =n(А) +n(В) = 3 + 4 = 7.

Нетрудно убедиться в том, что если В ? А, то n (ВґА) = n(А) - n(В),т.е. число элементов дополнения подмножества В до конечного множества А равно разности численностей этих множеств.

Пусть, например, А = {х, у, z,p,t}, а В = { х,p,t}. Получаем n(А) = 5,n(В) = 3. Тогда n(ВґА) =n(А) -n(В) = 5 - 3 = 2.

Формула (1) позволяет находить число элементов в объединении конечных непересекающихся множеств. А если множества А и В имеют общие элементы, то как найти число элементов в их объединении?

Пусть, например, А = {х, у, z}, а В = {х,z, р,s,k}. Тогда А? В = {х, у,z, р,s,k}, т.е.n(А) = 3,n(В) = 5, аn(А? В) = 2 и, значит, общие элементы множеств А и В в объединении этих множеств записаны только один раз.

В общем виде правило подсчета элементов в объединении двух конечных множеств может быть представлено в виде формулы:

n(А?В) = n(А) + n(В) - n(А ? В).(2)

Полученные формулы для подсчета числа элементов в объединении двух и более множеств можно использовать для решения текстовых задач следующего вида.

Задача. Из 40 студентов курса 32 изучают английский язык, 21 - немецкий язык, а 15 - английский и немецкий языки. Сколько студентов курса не изучает ни английский, ни немецкий языки?

Решение. Пусть А - множество студентов курса, изучающих английский язык, В - множество студентов курса, изучающих немецкий язык, С - множество всех студентов курса. По условию задачи: n(А) = 32,n(В) = 21,n(А? В) = 15,n(С) = 40. Требуется найти число студентов курса, не изучающих ни английского, ни немецкого языка.

1 способ.

1) Найдем число элементов в объединении данных множеств А и В. Для этого воспользуемся формулой (2):

n(А?В) =n(А) +n(В) -n(А? В) = 32 + 21 - 15 = 38.

2) Найдем число студентов курса, которые не изучают ни английский, ни немецкий языки: 40 - 38 = 2.

2 способ.

1) Изобразим данные множества при помощи кругов Эйлера и определим число элементов в каждом из непересекающихся подмножеств (рисунок).

Рис. 2

Так как в пересечении множеств А и В содержится 15 элементов, то студентов, изучающих только английский язык, будет 32 - 15 = 17, а студентов, изучающих только немецкий язык, 21 - 15 = 6. Тогда n(А?В) = 17 + 15 + 6 = 38, и, следовательно, число студентов курса, которые не изучают ни английский, ни немецкий языки, будет 40 - 38 = 2.

1.4 Число элементов в декартовом произведении конечных множеств

Нам известно, как находят декартово произведение конечных множеств. Например, если А = {х, у, z}, а В = {m,p}, то А х В = {(х,m), (х, р), (у,m), (у, р ), (z,m), (z, р)}. Чтобы ответить на вопрос: «Сколько элементов в полученном множестве?», достаточно пересчитать их. А как определить число элементов в декартовом произведении множеств, не образуя его и не обращаясь к пересчету элементов?

Можно доказать, что если в множестве А содержится а элементов, а в множестве В - b элементов, то в декартовом произведении множеств А и В содержится а* bэлементов, т.е.

n(А х В) = n(А) * n(В) = а * b. (3)

Правило распространяется на случай t множеств, т.е.

n(Ах А х …х Аt) =n(А)*n(А) *…*n(Аt).

Например, если в множестве А содержится 3 элемента, в множестве В - 4 элемента, в множестве С - 5 элементов, то в их декартовом произведении будет содержаться 3*4*5 = 60 упорядоченных наборов из трех элементов.

Полученные формулы можно использовать при решении задач.

Задача 1. У Маши 3 различных юбки и 4 различных кофты. Сколько различных комплектов, состоящих из юбки и кофты, она может составить?

Решение. Пусть А - множество юбок у Маши, В - множество кофт. Тогда, по условию задачи, n(А) = 3,n(В) = 4. Требуется найти число возможных пар, образованных из элементов множества А и В, т.е.n(А х В). Но согласно правилу n(А х В) =n(А)*n(В) = 3 * 4 = 12. Таким образом, из 3 юбок и 4 кофт Маша может составить 12 различных комплектов.

Задача 2. Сколько двузначных чисел можно записать, используя цифры 5, 4 и 7?

Решение. Запись любого двузначного числа состоит из двух цифр и представляет собой упорядоченную пару. В данном случае эти пары образуются из элементов множества А = {5, 4, 7}. В задаче требуется узнать число таких пар, т.е число элементов в декартовом произведении А х А. Согласно правилу n(А х А) =n(А)*n(А) = 3 * 3 = 9. Значит, двузначных чисел, записанных с помощью цифр 5, 4 и 7, будет 9.

Часто при решении задач, аналогичных рассмотренным выше, требуется не только ответить на вопрос о том, сколько существует возможных вариантов ее решения, но и осуществить перебор этих вариантов. Например, в задаче 2 можно предложить записать все двузначные числа, используя цифры 4, 5 и 7.

Существует единый подход к осуществлению такого перебора - строится схема, называемая деревом возможных вариантов. Она будет иметь вид:

Рис. 3

2. Анализ прикладных задач решаемых с помощью принципа включений и исключений

Примеры решения задач с применением принципа включений-исключений.

Задача. Каждый студент первого курса обязан изучать хотя бы один иностранный язык. На юридическом факультете изучаются либо английский, либо немецкий язык. Из 94 первокурсников юридического факультета 76 человек изучают английский язык, 34 - изучают немецкий. Сколько студентов изучают два языка?

Решение.

Обозначим А - множество студентов, изучающих английский язык; В - множество студентов, изучающих немецкий язык. Множество всех первокурсников равно АВ.

Множество, изучающих два языка AB. Воспользуемся формулой

m(AB) = m(A) + m(B) - m(AB).

Из условия задачи m(A)=76, m(B)=34, m(AB) =94. Поэтому:

m(AB)= 76+34-94=16.

Задача. В одном из городов Украины часть жителей говорит только по-русски, часть - только по-украински, часть говорит на обоих языках. Известно, что 90% жителей говорит по-русски, а 80% - по-украински. Какой процент жителей говорит на обоих языках? Какой процент говорит только по-русски? Какой процент говорит только по-украински? Решение. Введем ряд обозначений. Пусть N - множество жителей, говорящих по-русски, а K - по-украински. По условию задачи m(N) = 90%, m(K) = 80%, а m(NK) = 100% - это общее число жителей. Процент двуязычных жителей m(NK) может быть определен из соотношения:

m(NK) = m(N) + m(K) -m(NK)

100%=90%+80%- m(NK)

m(NK)=90%+80%-100%=70%.

Множества одноязычных жителей определяются следующими выражениями:

Русскоязычные - N\(NK), говорящие только по-украински - K\(NK). Поскольку в обоих случаях пересечение (NK) является подмножеством множеств N и K, то количество одноязычных жителей может быть получено по формулам:

m(N\(NK))= m(N)- m(NK)=90%-70%=20%

m(K\(NK))= m(K)- m(NK)=80%-70%=10%

Задача. Итоговое рейтинговое задание по курсу «Математика и информатика» содержало три задания: по MS Office, по математике и по Справочной правовой системе (СПС). Результаты проверки задания у 40 студентов представлены ниже.

Табл. 1

Выполнены задания	Количество выполнивших	Выполнены задания	Количество выполнивших
MS Office	20	MS Office и СПС	7
СПС	18	MS Office и математика	8
Математика	18	СПС и математика	9

Известно также, что ни одного задания не выполнили трое. Сколько студентов выполнили все три задания? Сколько студентов выполнили ровно два задания?

Решение. Введем обозначения: N- множество студентов, выполнивших задание по MS Office; K - выполнивших задание по СПС; P - выполнивших задание по математике; x - число студентов, выполнивших все три задания. Из рисунка можно отметить следующие данные: (7-x) - число студентов, выполнивших задания MS Office и СПС, но не по математике; (8-x) - число студентов, выполнивших задания MS Office и математике, но не по СПС, (9-x) - по СПС и математике, но не по MS Office.

Если n, k, p - количество студентов, выполнивших только одно задание соответственно по MS Office, СПС и математике, то можно записать следующие выражения:

m(N)=20=16+n-x; m(K)=18=15+k-x; m(P)=18=17+p-x,

в результате решения которых получим следующие соотношения:

n=4+x; k=3+x; p=1+x.

Всего в рейтинге участвовало 40 студентов, трое не выполнили ни одного задания, это означает, что, по крайней мере, одно задание выполнили 37 студентов.

Множество студентов, выполнивших, по крайней мере, по одному заданию - NKP.

m(NKP) = 37.

m(NKP) = n+k+p+24-2x,

подставив в него выражения n, k и p через x, получим

4+x+3+x+1+x+24-2x=37

x=37-32=5.

Таким образом, число студентов, выполнивших все три задания равно 5.

Для определения количества студентов, выполнивших ровно два задания, из рисунка 3 получается следующее выражение

9-x+8-x+7-x=24-3x=24-15=9.

Задача. В штучном отделе магазина посетители обычно покупают либо один торт, либо одну коробку конфет, либо один торт и одну коробку конфет, В один из дней было продано 57 тортов и 36 коробок конфет. Сколько было покупателей, если 12 человек купили и торт, и коробку конфет?

Решение.

Обозначим через T множество покупателей, купивших торт, а через К - множество покупателей коробки конфет. Тогда множество всех покупателей определяется, как объединение вышеуказанных множеств Т К. А множество покупателей, сделавших две покупки, получается в результате пересечения тех же множеств Т К.

Их количество согласно условию задачи m(Т К) = 12.

Согласно теории m(Т К)=m(Т) + m(К) - m(Т К).

Подставив в эту формулу данные из условия задачи, получим m(Т К)= 57 + 36 - 12 = 81.

Задача.Каждый из студентов 1 курса в зимние каникулы ровно два раза был в театре на разных спектаклях, при этом спектакли А, В и С видели соответственно 50, 24 и 46 студентов. Сколько студентов на 1 курсе? Сколько из них видели спектакли А и В, А и С, В и С?

Решение.

Обозначим через S множество всех студентов первого курса, а через А, В и С соответственно множества студентов, посетивших спектакли А, В и С. С учетом введенных обозначений нам необходимо определить m(S), m(АВ), m(АС) и m(ВС).

Поскольку каждый студент посетил ровно два спектакля справедливо следующее соотношение m(S)=(m(A) + m(B) + m(C)) / 2 = (50 + 24 + 46) / 2 = 60. То есть, число студентов первого курса равно 60.

Поскольку каждый студент посетил два разных спектакля, то любой студент попадает либо в множество А, либо в множество В. Поэтому объединение этих множеств дает множество всех студентов, то есть S = AB. Если рассмотреть пары множеств А и С, В и С, то рассуждая аналогичным образом мы придем к справедливости соотношений

S = AС и S = ВС.

Согласно теории

m(А В)=m(А) + m(В) - m(А В).

Поэтому

m(АВ)=m(А) + m(В) - m(А В) = m(А) + m(В) - m(S) = 50 + 24 -60 =14.

Аналогично могут быть определены

m(А С) и m(В С).

m(А С)=m(А) + m(С) - m(А С) = m(А) + m(С) - m(S) = 50 + 46 -60 =36. m(В С)=m(В) + m(С) - m(В С) = m(В) + m(С) - m(S) = 24 +46 -60 =10.

Задача. Преподаватель решил узнать, кто из 40 студентов читал книги А, В и С. Результаты опроса оказались таковы: книгу А читало 25 человек, книгу В -- 22, книгу С -- также 22. Книгу А или В читали 33 студента, А или С -- 32, В или С -- 31; все три книги прочли 10 студентов. Сколько студентов прочли только по одной книге? Сколько студентов не читали ни одной из этих трех книг?

Решение.

Обозначим через А, В и С соответственно множества студентов, читавших книги А, В и С.

Из условий задачи имеем: m(A) =25, m(B) =22, m(C) = 22,

m(А В) =33, m(А С) = 32, m(В С) =31 и m(А В С) =10.

Если обозначить через D множество студентов, прочитавших, по крайней мере, одну из трех книг, то, очевидно, что для определения количества членов этого множества справедливо следующее выражение

m(D) = m(A) + m(B) + m(C) -m(АВ) - m(АС) - m(ВС) + m(АВС).

Если обозначить через Е множество студентов, прочитавших две или три книги, то, очевидно, что для определения количества членов этого множества справедливо следующее выражение

m(Е) =m(А В) + m(А С) + m(В С) - 2* m(А В С ).

К1 - количество студентов, прочитавших только по одной книге, может быть найдено по формуле К1 = m(D) - m(E), а число студентов, не прочитавших ни одной книги K0 = 40 - m(D).

Таким образом для определения всех искомых величин нам необходимо определить m(А В), m(А С) и m(В С).

Согласно теории

m(А В)=m(А) + m(В) - m(А В) = 25 + 22 - 33 = 14,

m(А С)=m(А) + m(С) - m(А С) = 25 + 22 - 32 = 15,

m(В С)=m(В) + m(С) - m(В С) = 22 + 22 - 31 = 13.

Подставим полученные результаты в вышеприведенные формулы

m(D) = m(A)+ m(B) + m(C) -m(АВ) - m(АС) - m(ВС) + m(АВС) =25 + 22 + 22 -14 - 15 -13 +10 = 37,

m(Е) =m(АВ) + m(АС) + m(ВС) - 2* m(АВС ) = 14 + 15 + 13 - 2 * 10 = 22,

К1=m(D) - m(E) =37 - 22=15, K0 = 40 - m(D) =40 - 37= 3.

Задача. В течение недели в кинотеатре демонстрировались фильмы А, В и С. Из 40 студентов, каждый из которых просмотрел либо все три фильма, либо один из трех, фильм А видели 13, фильм В -- 16, фильм С -- 19. Найти, сколько студентов просмотрели все три фильма.

Решение.

Обозначим через А, В и С соответственно множества студентов, посмотревших фильмы А, В и С.

Из условия задачи имеем: m(A)=13, m(B) =16, m(C) = 19,

m(А В С) = 40.

Требуется определить m(А В С).

Из соотношения множеств, отображенного на диаграмме, можно заключить, что справедливо следующее равенство

m(А В С) = m(A) + m(B) + m(C) -2* m(А В С).

Поэтому

m(АВС) = (m(A) + m(B) + m(C) - m(АВС))/2 = (13 + 16 + 19 - 40) / 2 = 4.

Заключение

В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую совокупность явлений, предметов и объектов реального мира. Сами множества так же могут объединяться во множества. Например, математики говорят о множестве фигур на плоскости, о множестве тел в пространстве, но каждую фигуру, каждое тело они мыслят как множество точек.

Суть понятия “множество” вполне передается словами: “совокупность”, “собрание”, “набор” и т.д. Однако, как абстрактное математическое понятие “множество” неопределимо.

Несмотря на это, определить какое-либо конкретное множество - задача не из трудных. Определить любое конкретное множество - значит определить, какие предметы (явления, объекты) принадлежат данному множеству, а какие не принадлежат. Иначе говоря, всякое множество однозначно определяется своими элементами.

Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

Система аксиом теории множеств была создана для решения задачи обоснования базовых положений современной математики. Таким образом существующие разделы математики можно считать a priori непротиворечивыми, поскольку все их доказанные высказывания логически могут быть сведены к аксиомам. В этом отношении аксиоматика выполнила свое предназначение.

Литература

1. Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. -- М. : «Вильямс», 2006. С. 501-502 --960с.

2. Боровков А.А. Теория вероятностей. -- 2-е изд. -- М.: «Наука», 2006. -- С. 24. -- 431с.

3. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика, Изд. 4-е, исправленное - МЦНМО, 2013 - 307с.

4. Виленкин Н.Я. Популярная комбинаторика. -- М. : Наука, 2005. С. 269-271 - 304с.

5. Ерош И.Л. Дискретная математика. Комбинаторика -- СПб. : СПбГУАП, 2001. С. 105-107 -- 237c.

6. Липский В. Комбинаторика для программиста. -- М. : Мир, 2008. С. 200-203 -- 213с.

7. Райгородский А.М. Линейно-алгебраические и вероятностные методы в комбинаторике. -- Летняя школа «Современная математика» . -- Дубна: 2006. С. 27 - 206с.

8. Раизер Г.Дж. Комбинаторная математика. -- пер. с англ. . -- М. : 2006. С. 54 - 103с.

Размещено на Allbest.ru

...