Материал: Дискретная математика теория и практика

в) {1, 2}и {1, 2, {1, 2}}; г) Ø и {1, 2, {1}, {Ø}}; д) Ø и {Ø}; е) Ø и {{Ø}} ;

ж) {1, 2}и {1, 2}.

4. Известно, что x A . Следует ли отсюда, что:

а) x A ∩ B ; б) x A B .

5.Известно, что y A B . Следует ли отсюда, что y A ?

6.Известно, что z A . Следует ли отсюда, что z A \ B ?

7.Даны множества A = {a, b, c, d}, B = {a, b, 4}, C = {4, 2, c}, D = {a, b, 3},

E = {1, b}. Найдите a, b, c, d, зная, что B A, C A, D A, E B.

8.Изобразите с помощью кругов Эйлера – Венна, в каком отношении находят-

ся множества: U – множество четырехугольников плоскости; A – трапеций; B – параллелограммов; С – ромбов; D – прямоугольников; E – квадратов; F – четырехугольников с перпендикулярными диагоналями, G – четырехугольников, диагонали которых делят друг друга пополам.

9. Найдите A B, A ∩ B, A \ B, B \ A, A B, A , B , если

A = {1, 2, 3}, B = {2, 3, 4, 5}, U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

10.Найдите A B, A ∩ B, A \ B, B \ A, если:

a) A = {a, b, c, d, e}, B = {a, c, e}; б) A = {a, b, c, d, e}, B = {k, l, m}; в) A = {a, b, c, d, e}, B = .

11.Найдите A B, A ∩ B, A \ B, B \ A, если а) A = [2; +∞), B = (1; 7];

б) A = [−7; −4], B = (0; 3); в) A = (−∞; 10), B =[−1; 5); г) A=[0; 3], B=[3; 6).

12.Даны множества A = {1, 2, 4, 6, 8}, B = {3, 4, 6}, C = {1, 5, 7},

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Найти: а) (A ∩ B)\ (A C ); б) (A C )\ (A ∩ B); в) B \ (A C ); г) A B ; д) A C .

13.Упростить выражения, используя свойства операций над множествами:

а) (A ∩ B ∩ C) (A ∩ B ∩ C ) B C ;

б) ( A B) ∩ ( A B) ∩ ( A B) ;

в) A ( A B ∩ C) (B ∩ ( A C)) .

г) (A ∩ B ∩ C ∩ D) (A ∩ C ) (B ∩ C ) (C ∩ D) ;

д) (A B C )∩ (A ∩ B ∩ C )∩ ( A С );

е) A A A.

14. В классе 32 учащихся. Из них 18 посещают химический кружок, 12 – биологический, 8 учеников не посещают ни одного из этих кружков. Сколько учени-

22

ков посещают и химический, и биологический кружок? Сколько учащихся посещают только химический кружок?

15.В группе 30 студентов, из них 18 увлекаются плаванием, а 17 – волейболом. а) Каким может быть минимальное число студентов, увлекающихся обоими видами спорта?

б) Каким может быть минимальное число студентов, увлекающихся хотя бы одним видом спорта?

16.Среди написанных на доске чисел, полученных случайным образом, 65% делятся на 2, 70% – на 3, 75% – на 5. Каков наименьший процент чисел, кратных 30?

17.Все студенты первого курса КГТУ специальности «ИС» изучают три языка программирования. В этом году 19 студентов предпочли изучать Pascal, 14 выбрали Basic, а 17 решили заниматься Delphi. Кроме того, было 4 студента, слу-

шающих курс по Pascal и Basic, трое изучают Pascal и Delphi, трое – Delphi и Basic. Известно, что никто из студентов не отважился посещать сразу три курса. Сколько студентов в группе «ИС»? Сколько из них были увлечены только

Delphi?

18.Опрошено 220 аквариумистов, 85 из них разводят дома сомов, 95 предпочитают гуппи, 100 – золотых рыбок, 26 – сомов и золотых рыбок, 22 – гуппи и золотых рыбок, 17 – сомов и гуппи, 5 опрошенных любуются в своем аквариуме на все три вида рыбок.

а) Сколько аквариумистов держат в своем аквариуме сомов, но не имеют гуппи?

б) Сколько аквариумистов разводят сомов или гуппи, но не любят золотых рыбок?

в) У скольких аквариумистов нет ни сомов, ни гуппи? г) Сколько аквариумистов разводят не только гуппи?

д) У скольких аквариумистов есть гуппи и золотые рыбки, но нет сомов?

19.Статисты опросили 100 посетителей туристического агентства «Золотой пляж». Выяснилось, что за последние 5 лет 50 человек отдыхали в Турции, среди которых 20 человека были еще и в Греции, 18 человек еще и в Египте, и пять человек побывали за пять лет во всех трех упомянутых странах. С достопримечательностями Греции из всех опрошенных познакомились 50 человек, среди которых 26 человек побывали только в двух странах. Сколько человек посетили страну пирамид?

20.По итогам экзаменов из 40 студентов отличную оценку по математике имели 11 студентов, по физике – 15, по химии – 13, по математике и физике – 4, по математике и химии – 3, по физике и химии – 3, по всем трем предметам – 1. Сколько студентов получили хотя бы по одной отличной оценке?

21.В мае было 12 дождливых, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, 2 ветреных и холодных дней, а один день был и дождливый, и ветреный, и холодный. В течение скольких дней в мае было тепло без ветра и без дождя?

22.Каждый из 100 костромичей, отдыхающих этим летом в Анапе, был на экскурсиях, в дельфинарии или в аквапарке. Из них аквапарк посетили 67 человек,

23

экскурсии – 82, дельфинарий – 67, экскурсии и дельфинарий – 53, экскурсии и аквапарк – 58, дельфинарий и аквапарк – 51. Сколько костромичей было на всех трех мероприятиях?

23.Староста курса представил следующий отчет о физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30, шахматная секция – 28, футбольная и баскетбольная – 16, футбольная и шахматная – 18, баскетбольная и шахматная – 17. В трех секциях одновременно занимаются 15 человек. Объясните, почему отчет не был принят?

24.В клубе по борьбе с человеческими страхами из 100 человек 60 боятся пауков, 54 – змей, 55 – мышей, 38 боятся пауков и змей, 34 – змей и мышей, 40 – пауков и мышей, и 20 человек боятся замкнутого пространства.

а) Сколько человек боится пауков или мышей, но не боятся змей? б) Сколько человек боится только одного вида животных?

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

д) Сколько человек боится только змей?

25.Среди счастливчиков, кому повезло поймать золотую рыбку, пожелавших новую квартиру оказалось 18 человек, дорогую машину – 14, хорошую работу – 28, квартиру и машину – 5, квартиру и работу – 10, машину и работу – 8, все три желания загадало 3 человека. Сколько всего человек поймали золотую рыбку? Сколько среди них загадавших только одно желание?

26.В лыжной, хоккейной и конькобежной секциях 38 студентов потока. Известно, что в лыжной секции занимается 21 студент, среди которых 3 студента занимались еще в конькобежной секции, 6 студента еще в хоккейной секции и один студент занимался одновременно во всех трех секциях. В конькобежной секции занимались 13 студентов, среди которых 5 студентов занимались одновременно в двух секциях. Сколько студентов занималось в хоккейной секции?

27.Преподаватель решил узнать, кто из 40 студентов курса читал книги А, В и С. Результаты опроса оказались таковы: книгу А читали 25 студентов, книгу В

– 22, книгу С – также 22. Книгу А или В читали 33 студента, А или С – 32, В или С – 31; все три книги прочли 10 студентов. Сколько студентов прочли только по одной книге? Сколько студентов не читали ни одной из этих трех книг?

28.В группе 25 учащихся. Из них 13 лыжников, 8 пловцов, 17 велосипедистов. Причем каждый спортсмен занимается только двумя видами спорта и учится на «3» или на «4». В группе 6 круглых отличников. Сколько в группе спортсменов? Сколько в группе неуспевающих?

Глава 2. Комбинаторика

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

24

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

Решение многих комбинаторных задач основано на следующих двух правилах.

2.1. Правила суммы и произведения

Пусть Х – конечное множество такое, что |X| = n. Тогда говорят, что объект х из Х может быть выбран n способами. Пусть Х1, …, Хn – попарно непересекающиеся множества, то есть Хi ∩ Xj = при любых i ≠ j. Тогда, очевидно,

В комбинаторике этот факт называется правилом суммы. Для n = 2 оно формулируется следующим образом: «Если объект x может быть выбран m способами, а объект y – другими n способами, то выбор “либо x, либо y” может быть осуществлен m + n способами».

Другим часто применяемым в комбинаторике правилом является правило произведения. Сформулируем и докажем частный случай этого правила для кортежа длины 2: «Если объект x может быть выбран m способами и после каждого из таких выборов объект y в свою очередь может быть выбран n способами, то выбор упорядоченной пары (x, y) может быть осуществлен m · n способами».

Доказательство. Пусть X = {а1, …, am} – множество элементов, из которых выбирается объект x, и Xi ={(x, y)| x = ai, y может быть выбран n способа-

зом: «Если объект x1 может быть выбран n1 способами, после чего объект x2 может быть выбран n2 способами и для любого i, где 2 ≤ i ≤ m − 1, после выбора объектов x1, ..., xi объект xi+1 может быть выбран ni+1 способами, то выбор кортежа (x1, x2, ..., xm) длины m может быть осуществлен n1 · n2 · … · nm способами».

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

Пример 2.1. В одной группе учится 25 человек, в другой – 20. Сколькими способами можно выбрать на конференцию:

a) одного делегата от двух групп;

б) по одному делегату от каждой группы?

25

Решение. Начальный этап решения обеих задач состоит в выборе делегата от первой группы, следующий этап – определение представителя второй группы. В задании под буквой а) существенным является то, что оба действия не могут быть выполнены одновременно, поскольку они взаимно исключают друг друга. Должен быть выполнен либо первый этап, либо второй. Рассуждения соответствуют правилу сложения, по которому получают 20 + 25 = 45 способов. Аналогично, для решения задания под буквой б) необходимо применить правило произведения, согласно которому выбрать по одному делегату от каждой группы можно 20 25 = 500 способами.

2.2. Размещения и сочетания

Определение 2.1. Набор элементов xi1 , …, xik из множества

Х = {x1, .., xn} называется выборкой объема k из n элементов или (n, k)-

выборкой.

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

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

Определение 2.3. Выборка называется неупорядоченной, если порядок следования элементов в ней не является существенным.

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

В выборках могут допускаться или не допускаться повторения элементов. Определение 2.4. Упорядоченная (n, k)-выборка, в которой элементы мо-

гут повторяться, называется (n, k)-размещением с повторениями. Определение 2.5. Упорядоченная (n, k)-выборка, элементы которой по-

парно различны, называется (n, k)-размещением без повторений.

Определение 2.6. Перестановкой без повторений из n элементов (или перестановкой множества X мощности n) называется (n, n)-размещение без повторений.

Определение 2.7. Неупорядоченная (n, k)-выборка, в которой элементы могут повторяться, называется (n, k)-сочетанием с повторениями.

Определение 2.8. Неупорядоченная (n, k)-выборка, элементы которой попарно различны, называется (n, k)-сочетанием без повторений.

Заметим, что любое (n, k)-сочетание без повторений можно рассматривать как k-элементное подмножество n-элементного множества.

Пример 2.2. Пусть Х = {a, b, c}. Тогда

1.(a, a),(a, b),(a, c),(b, a),(b, b),(b, c),(c, a),(c, b),(c, c) – (3,2)-размещения с по-

вторениями;

2.(a, b), (a, c), (b, a), (b, c), (c, a), (c, b) – (3,2)-размещения;

26