22.3 Приклади розв’язання типових завдань

1. На потоці факультету КН навчається 100 студентів. З них 48 знають мову С#, 35 – мову Java і 27 – обидві мови. Скільки студентів не знають жодної мови?

Результат можна отримати так. Побудуємо діаграму (рис. 22.1), на якій зобразимо прямокутник, відповідний загальній кількості студентів (100 чол.) і дві пересічні області А і В по 48 і 35 чоловік відповідно (які знають С# і Java). На діаграмі загальна частина цих двох областей відповідає 27 – кількості студентів, які знають обидві мови (рис. 22.1). Потрібно знайти область прямокутника, що не входить ані в область А, ані в область, яка відповідає студентам, що не знають обидві мови програмування. Очевидно, що N = 100 – 48 – 35 + 27 = 44.

Рисунок 22.1

2. Скільки чисел від 1 до 100 не діляться на 5 та 7?

Скористаємося формулою про включення й виключення. Під першою властивістю чисел розумітимемо подільність на 5, під другим – подільність на 7. На 5 діляться 20 чисел, тобто кожне п'яте число. На 7 діляться 14 чисел, тобто кожне сьоме число. На 5 і 7, тобто на 35, діляться два числа. Отже, не діляться на 5 і 7: 100 – 20 – 14 + 2 = 68 чисел.

3. Староста однієї групи подав кураторові такі дані про студентів: «У групі навчаються 45 студентів, у тому числі 25 юнаків. 30 студентів навчаються на добре та відмінно, в тому числі 16 юнаків. Наукою займаються 28 студентів, в тому числі 18 юнаків та 17 студентів, які навчаються на добре та відмінно. 15 юнаків, які навчаються на добре та відмінно водночас, займаються спортом».

Через декілька днів його викликав до себе куратор (який викладав дискретну математику) і сказав, що у відомостях є помилка. Спробуємо виявити, як він про це дізнався. Для цього підрахуємо, скільки дівчат не займаються наукою та отримують час від часу трійки чи двійки. Позначимо через α₁ належність до чоловічої статі, через α₂ – добру успішність та через α₃ – зацікавленість наукою. Знайдемо, чому дорівнює N( ). За умовою завдання маємо N(α₁)=25, N(α₂)=30, N(α₃)=16, N(α₁α₃)=18, N(α₂α₃)=17, N(α₁α₂α₃)=15. Отже, за формулою включення й виключення отримуємо, що N( )=45-25-30-28+16+18+17-15=-2.

Але негативною відповідь бути не може! Тому в наведених відомостях є внутрішнє протиріччя, вони невірні.

22.4 Контрольні запитання та завдання

1. Сформулюйте головну теорему комбінаторики (про включення та виключення). Запишіть формулу.

3. Запишіть формулу включення й виключення для випадку, коли кількість властивостей, що цікавлять, дорівнює 5.

4. Проведіть відповідно до діаграми Ейлера доведення формули включення й виключення для трьох властивостей: .

5. Доведіть справедливість формули включення й виключення.

6. Наведіть приклади використання формули включення й виключення.

22.5 Приклади аудиторних і домашніх задач

1. Іспит з дискретної математики складали 250 абітурієнтів. Оцінку нижче п'яти балів одержали 180 абітурієнтів, а витримали іспит 210 абітурієнтів. Визначіть, скільки абітурієнтів одержали оцінку 3 або 4.

2. У бібліотеці 1400 підручників з дискретної математики. З них 1250 містять теорію графів, 925 – комбінаторику. 60 підручників не містять ні комбінаторику, ні теорію графів. Визначіть, скільки підручників містять і теорію графів, і комбінаторику.

3. На потоці 100 студентів. З них 15 не склали математику, 12 – фізику, 15 – програмування, 12 студентів не склали математику й фізику, 8 – фізику і програмування, 10 – математику й програмування. 80 студентів склали всі іспити. Визначіть, скільки студентів неуспішно закінчили сесію (тобто не склали 3 іспити).

4. У 45 – процесорній ЕОМ 19 мікропроцесорів обробляють текстову інформацію, 27 – графічну, 21 – символьну, 12 мікропроцесорів одночасно обробляють графічну й текстову, 7 – текстову й символьну, 5 – графічну й символьну, а частина мікропроцесорів одночасно обробляють графічну, текстову й символьну інформацію. Визначіть, скільки процесорів є універсальними.