Круги Ейлера. Задачі комбінаторного характеру

Поняття множини. Операції над множинами

Поняття множини належить до первісних понять математики, якому не дається означення. Множину можна уявити собі як су­купність деяких предметів, об'єднаних за довільною характерис­тичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій.

Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь­кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож­на позначити буквою М (чи будь-якою великою буквою латин­ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}.

Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис­лом Наприклад, множина М цифр десяткової нумерації скінчен­на і містить десять елементів. У нескінченній множині - нескін­ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

Множина, в якій немає жодного елемента, називається порож­ньою і позначається символом 0. Наприклад, множина точок перетину двох паралельних прямих - порожня множина.

Множину задають двома основними способами:

1) переліченням всіх її елементів;

2) описанням характеристичної властивості її елементів. Наприклад: а) В = {o,1,¡} - множина, задана переліченням елементів; б) X - множина коренів квадратного рівняння х² = 25. Множина X задана характеристичною властивістю елементів - бути коренем рівняння х*х = 25". Цю саму множину можна зада­ти і переліченням її елементів: X = {-5; 5}.

Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|= 5. Отже, X = Y.

Над множинами виконуються певні операції (дії). Зазначимо три з них.

Переріз множин.

Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен­тів, які належать коленій з даних множин А і В.

Приклад 1. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників чис­ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Об'єднання множин.

Об'єднанням (або сумою) двох мно­жин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.

Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.

Операції над множинами широко використовуються в мате­матиці та інших науках, а також у практиці. Наприклад, розв'яз­ками системи рівнянь є переріз множин розв'язків кожного рів­няння, а об'єднання їх є множиною розв'язків сукупності рів­нянь.

Віднімання множин. Доповнення множини.

Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.

Позначається це так: С = А \ В і читається: "С є різницею А і В".

Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6},  тоді С = А \ В= {8, 12};

б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};

в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};

Різниця С = А \ В називається доповненням множини В відносно множини А і позначаєть­ся С=А\В.

Дуже важливими для практичних  задач є формули  підрахунку кількості різних елементів у декількох множинах, що містять спільні елементи, тобто кількості елементів в об’єдананні двох або трьох множин.

Кількість елементів об'єднання  п(АÈВ)  будь-яких двох скін­ченних множин А і В обчислюється за формулою:

п(АÈВ) = п(А) + п(В) - п(АÇВ).

Для будь-якої трійки скінченних множин А₁, А₂, А₃ має місце формула кількості елементів множини п(A₁ È А₂ ÈА₃) , що є об’єднанням трьох множин, тобто  A₁ È А₂ ÈА₃:

п(A₁ È А₂ ÈА₃) = п(А₁) + п(А₂) + п(А₃) - п(А₁ÇА₂) - п(А₁ ÇА₃) - п(А₂ ÇА₃) + п(А₁ÇА₂ ÇА₃).

Наводимо приклад використання поданих вище формул.

Задача 7. У лабораторії науково-дослідного інституту працює декілька чоловік, причому кожний з них знає хоча б одну іноземну мову, 6 чоловік знають англійську, 6 ‒ німецьку, 7 ‒ французьку, 4 знають англійську і німець­ку, 3 ‒ німецьку і французьку, 2 ‒французьку і англійсь­ку, один чоловік знає всі три мови. Скільки чоловік пра­цює в лабораторії? Скільки з них знає лише англійську мову? Скільки чоловік знає лише одну мову?

Розв'язання.

Позначимо п(А), п(Н), п(Ф) кількість співробітників у лабораторії, які знають англійську, німецьку та фран­цузьку  мови   відповідно,  а   п(НÇФ),  п(АÇН),  п(АÇФ), п(АÇНÇФ) ‒  кількість чоловік, що знають по дві і три мови відповідно. Тоді, за правилом суми, загальне число співробітників у лабораторії дорівнює

m = п(А)+ п(Н) + п(Ф) - п(НÇФ) - п(АÇН) - п(АÇФ) + п(АÇНÇФ)  = 6 + 6 + 7 - 3 - 4 - 2 + 1 = 11.

Тільки англійську та німецьку мови знають

п_АН = п(А ÇН) ‒ п(АÇН ÇФ) = 4-1= 3 чоловіка, тільки англійську і французьку

п_АФ = п(АÇФ) - п( АÇН ÇФ) = 2-1= 1 чоловік. Тоді тільки англійську мову знає

п_А = п(А) - п_АН  – п_АФ - п( АÇН ÇФ) =  6-3 -1-1 =1 чоловік. Тільки німецьку і французьку знають

п_НФ = п(Н ÇФ) - п(АÇНÇФ) = 3 ‒ 1 = 2 чоловіки. Тоді більше однієї мови знають

k = п(АÇНÇФ) + п_АН + п_АФ + п_НФ = 1 +3+1+2 =7 чоловік, її тільки одну мову  p = п - т = 11- 7 = 4 чоловіка.

Наводимо приклади задач використання поданих вище формул.

Задача 1. У групі зі 100 туристів 70 знають ан­глійську мову, 45 - французьку і 23 - знають обидві мови. Скільки туристів у групі не знають ні англійської, ні французької?

Задача 2. В одному з відділів магазину покупці зазвичай купляють або один торт, або коробку цу­керок. Одного дня було продано 57 тортів та 36 коробок цукерок. Скільки було покупців, якщо 12 з них придбали і торт, і коробку цукерок?

Задача 3. У спортивному таборі 65  дітей вміють грати в футбол, 70  — у волейбол і 75  — у баскетбол. Всьогодітей у табобі 100.  Яка найменша кількість дітей, які вміють грати і у футбол, і у баскетбол, і у волейбол?

Задача 4. Кожен учень класу на зимових кані­кулах відвідав театр двічі, при цьому спектаклі А, В та С бачили відповідно 25, 12 та 23 учні. Скільки учнів навчається у класі? Скільки з них відвідали спектаклі А та В, А та С, В та С?

Задача 5. На уроці літератури вчитель спробу­вав дізнатися, хто з 40 учнів класу читав книги А, В та С. Результати опитування виявилися такі: книгу А читали 25 учнів, книгу В - 22 учні, книгу С - також 22 учні. Книги А або В читали 33 учні, А або С - 32 учні, В або С - 31 учень; усі три книги прочитали 10 учнів. Скільки учнів прочитали одну книгу? Скільки учнів не прочитали жодної з трьох книг?

Задача 6. Опитування 100 студентів показало такі результати про кількість студентів, які вивчають іно­земні мови: англійську - 28; німецьку — 30; фран­цузьку - 42; англійську та німецьку - 8; англійську та французьку — 10; німецьку та французьку — 5; всі три мови - 3 студенти. Скільки студентів не вивчає жодної мови? Скільки студентів вивчає тільки французьку мову? Скільки студентів вивчає тільки німецьку мову? Скільки студентів вивчає тільки анг­лійську мову?

Задача 7. Протягом тижня в кінотеатрі демонст­рувалися фільми А, В та С. З 40 школярів, кожен з яких подивився або всі три фільми, або один з трьох, фільм А дивилися 13 учнів, фільм В – 16, фільм С – 19. Скільки учнів переглянули всі три фільми?

Задача 8. У класі з 40 учнів 30 уміють плавати, 27 уміють грати у шахи і тільки 5 не вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?

Дуже важливу роль в комбінаторіці відіграє індуктивний метод обгрунтування правил-алгоритмів та формул.

Задача 8. Довести, що на площині n прямих, серед яких жодні три не перетинаються в одній точці, а жодні дві не паралельні, поділяють площину на 1 + 0,5n(n + 1) частин.

Доведення (методом математичної індукції):

1)Одна пряма ділить площину на 2 = 1+0,5 ∙ 1 ∙(1 +1)  частини, тобто твердження справджується для формули, якщо n = 1.

Можна за допомогою малюнків впевнитися, що формула вірна і для двох або для трьох прямих.

2)Припустимо, що n прямих ділять площину на 1 + 0,5n(n+1) час­тин. Нова (n + 1)-а пряма перетне наявні n прямих у n точках,
що поділять нову пряму на (n + 1) частин. Отже, з наявних
1 + 0,5n(n + 1) частин площини буде перетнуто і поділено новою
прямою (n+1). Таким чином, при проведенні цієї прямої кількість частин, на які поділяється площина, зросте на (n + 1) і
дорівнюватиме:

1 + 0,5n(n + 1) + (n + 1) = 1 + 0,5(n + 1)(n + 2).