Зразки задач з КОМБІНАТОРИКИ

Скількома способами можна проїхати з міста А в місто В? Скільки різних слів в мові Мумбо-Юмбо? Скільки існує "симпатичних" чоти­рицифрових чисел? ... Скільки ... ? Такі та деякі інші, схожі на них, питання будуть обговорюватися в цій главі.

Почнемо з декількох простих задач.

1. В магазині "Все до чаю"  є п'ять різних чашок та 3 різних блюдця. Скількома способами можна купити чашку з блюдцем?

Розв'язок. Виберемо чашку. У комплекті з нею можна вибрати будь-яке з трьох блюдець. Тому є три різні комплекти, які мають ви­брану чашку. Оскільки чашок всього 5, то кількість різних комплектів дорівнює 15. (15 = 5∙3).     

2. В магазині "Все до чаю" є п'ять різних чашок та 3 різних блюдця та  4 чайні ложки. Скількома способами можна купити комплект з чашки, блюдця та ложки?

Розв'язок. Виберемо будь-який з 15 комплектів попередньої задачі. Його можна доповнити ложкою чотирма різними способами. Тому за­гальна кількість мождивих комплектів дорівнює 60 (60 = 15∙4 = 5∙3∙4).

3. В Країні Чудес є три міста: А, Б і В. З міста А в місто Б ведуть 6 доріг, а з міста Б у місто В – 4 дороги . Скількома способами можна проїхати від А до В?

Розв 'язок. 24 = 6∙4.

4. В Країні Чудес є чотири міста: А, Б і В, Г і декілька нових доріг. Скількома способами можна тепер добратися з міста А в місто В?

Розв 'язок. Виділимо 2 випадки: шлях проходить через місто Б або через місто Г. У кожному з цих випадків легко порахувати кількість різних маршрутів: в першому – 24, у другому – 6. Додаючи, отри­маємо загальну кількість маршрутів: 30.     

5. В магазині "Все до чаю" , як і раніше, продається 5 чашок, 3 блюдця та 4 чайні ложки. Скількома способами можна купити два предмети з різними назвами?

Розв'язок. Можливі три різні випадки: перший – купується чашка з блюдцем, другий – чашка з ложкою, третій – блюдце та ложка.  У кожному з цих випадків легко порахувати кількість можливих варіан­тів (в першому – 15, у другому  – 20, у третьому – 12). Додаючи, отримуємо загальну кількість можливих варіантів: 47.    

6. Назвемо натуральне число "симпатичним", якщо в його запису зустрічаються тільки непарні цифри. Скільки існує 4-цифрових "симпатичних" чисел?

Розв'язок. Зрозуміло, що одноцифрових "симпатичних" чисел рівно 5. До кожного одноцифрового "симпатичного" числа друга непарна цифра може бути дописана п'ятьма різними способами. Таким чи­ном, двоцифрових  "симпатичних" чисел 5∙5 = 25. Аналогічно, три цифрових "симпатичних" чисел 5∙5∙5 = 125, а чотирицифрових – 5∙5∙5∙5 = 625.

Зауваження. В цій задачі розв'язок має вигляд mⁿ. До такого розв'язку приводять задачі, в котрих на кожному з n місць може бути поставлений елемент з деякої m-елементної множини. Ці задачі часто спричиняють труднощі у школярів, які не завжди розуміють,  яке з чисел є основою степеня, а  яке показник.

Запропонуємо ще чотири подібні задачі.

7.  Монету кидають тричі.    Скільки різних послідовностей орлів та решок можна при цьому отримати? Відповідь: 2³=8.

8. Кожну клітинку квадратної таблиці 2x2 можна пофарбу­вати в чорний або білий колір. Скільки існує різних роафарбувань цієї таблиці?

Відповідь: 2⁴ = 16.

9. Скількома способами можна заповнити одну картку в ло­тереї "Спорт прогноз"? (В цій лотереї треба передбачити підсумок тринадцяти. спортивних матчів. Підсумок кожного матчу – перемога однієї з команд або нічия; рахунок не має значення.)

Відповідь: 2¹³.

10. Алфавіт племені Мумбо-Юмбо складається з трьох літер А, Б та В. Слово – будь-яка послідовність, яка складається не більше як з 4 літер. Скільки слів в мові племені Мумбо-Юмбо?

Вказівка. Підрахуйте окремо кількість одно-, дво-, три- та чотирилітерних слів.

Розв 'язок. 3¹+ 3² + 3³ + 3⁴ = 120.

Перейдемо до другого циклу задач.

11. У футбольній команді (11 чоловік) треба, вибрати капіта­на та його заступника. Скількома способами це можна зробити?

Розв 'язок. Капітаном може стати будь-хто з 11 футболістів. Після об­рання капітана на роль заступника можуть претендувати 10 чоловік, які залишилися. Таким чином, всього є 11∙10 = 110 різних варіантів виборів.     

Ця задача відрізняється від попередньої тим, що вибір капітана об­межує коло претендентів на роль заступника: капітан не може бути своїм заступником. Таким чином, вибори капітана та його заступника не виявляються незалежними  такими, як, наприклад, вибори чашки та блюдця в задачі 1.

Ось ще чотири задачі на цю тему.

12. Скількома способами можна зробити трикольоровий прапор з горизонтальними смугами однакової ширини, якщо є матерія шести різних кольорів?

Ров'язок. Колір для верхньої смуги прапору можна вибрати шістьма різними способами. Після цього для середньої смуги прапора зали­шається п'ять можливих кольорів, а потім для нижньої смуги пра­пора – чотири різні кольори. Таким чином, прапор можна зробити 6∙5∙4 = 120 способами.

13. Скількома способами можна поставити на шахову дошку білу та чорну  тури  так, щоб вони не били одна одну?

Розв'язок. Білу туру можна поставити на будь-яку з 64 кліток. Незалежно від розташування вона б'є 15 полів (включаючи поле, на якому вона стоїть.). Тому залишається 49 полів, на які можна поставити чорну   туру. Таким чином, всього  64∙49 = 3136 різних способів.

14. Скількома способами можна поставити на шахову дошку білого  і чорного королів так, щоб вийшла допустима правилами гри позиція.

Розв'язок.     Білого короля можна поставити на будь-яке з 64 полів. Але кількість  полів, котрі він при цьому буде бити, залежить від його розташування. Тому необхідно розглянути три випадки:

а)  якщо білий король стоїть в кутку (кутків всього 4), то він б'є 4 поля (включаючи те, на якому стоїть), і залишаються 60 полів, на які можна поставити чорного короля;

б) якщо білий король стоїть на кінці дошки, але не в кутку (таких полів – 24), то він б'є 6 полів, і для чорного короля залишається 58 можливих полів;

в)  якщо ж білий король стоїть не на кінці дошки (таких полів – 36), то він б'є 9 полів, і для чорного короля залишається 55 можливих полів.

Таким чином,  всього маємо 4∙60 + 24∙58 + 36∙55 = 3612 способів розставляння королів.

Займемося тепер підрахунком кількості способів, якими можна ро­зташувати в ряд n предметів. Такі розташування називаються пере­становками і відіграють помітну роль в комбінаториці та алгебрі. Але попередньо необхідно зробити невеликий відступ.

Нехай n – натуральне число, n! (читається "ен-факторіал") –  це добуток

1∙2∙3∙...∙n = n!. Таким чином,  0!=1,  1!=1,  2! = 1∙2=2, 3! = 1∙2∙3 = 6, 4! = 24, 5! = 120.

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

Вправа 1.  Чому дорівнює:

 а) 10!∙ 11;   б) n ! ∙( n + 1);  в) 3! – 4! – 0! –1! + 6!?

Вправа 2.  Обчислити а) 10!/8!; б) n!/(n - 1)! в) (n +1)!/(n - 1)!

Вправа 3. Доведіть, що, якщо р – просте число, то (р – 1)! не ділиться на р.

Слід мати на увазі, що для зручності написання деяких комбінатор­них тотожностей прийнято вважати, що 0! дорівнює 1.

Повернемося тепер до перестановок.

15. Скільки існує трицифрових чисел, в запису яких 1, 2, 3 зустрічаються рівно по одному разу.

Розв 'язок. Будемо міркувати так само, як при розв'язуванні задач по­переднього циклу. На перше місце можна поставити будь-яку з трьох цифр, на друге – будь-яку з двох, які залишилися, а на третє останню з цифр, яка залишилася. Таким чином, всього виходить 3∙2∙1 = 3!

16. Скількома способами можна викласти в ряд червону, чор­ну, синю та зелену кульки?

Розв 'язок. На перше місце можна покласти будь-яку з чотирьох ку­льок, на друге – будь-яку з трьох, які залишилися, на третє –  будь-яку з двох, які залишилися, а на четверте – останню кульку, яка залишилася. Таким чином, розв'язок: 4∙3∙2∙1 = 4!.     

Розмірковуючи так само, як при розв'язуванні двох останніх задач, легко довести, що n різних предметів можна викласти в ряд n∙( n –1)( n – 2)∙... ∙2∙1 різними способами, тобто кількість перестановок з n елементів дорівнює n!.

Для зручності формулювання задач наступного циклу умовимося називати словом будь-яку скінченну послідовність літер українського алфавіту. Скажімо, використовуючи літери А, Б, В рівно по одному разу, можна скласти 6 слів: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА; вико­ристовуючи літеру А двічі, а літеру Б один раз – три слова: ААБ, АБА, БАА. В наступних п'яти задачах необхідно з'ясувати, скільки різних слів можна отримати, переставляючи літери того або іншого слова.

17. Скільки різних слів можна отримати, переставляючи літери  слова "ВЕКТОР"?

Розв 'язок. Оскільки всі літери слова різні, то всього можна отримати 6!=720 слів.

 18. Скільки різних слів можна отримати, переставляючи літери  слова "ЛІНІЯ"?

Розв'язок. У цьому слові дві літери І, а всі інші літери різні.   Тимчасово будемо вважати різними і літери І, позначивши їх як І₁  та І₂. При цьому припущенні отримаємо 5! = 120 різних слів. Але ті слова, які дістаються одне з одного тільки переставленням літер І₁  та І₂, насправді однакові, Таким чином, отримані 120 слів розбиваються на пари однакових.    Тому різних слів всього 120 : 2 = 60.    

19.    Скільки різних слів можна отримати, переставляючи літери  слова "ПАРАБОЛА"?

Розв'язок. Вважаючи три літери А цього слова різними (А1, А2, А3), дістанемо 8!  різних слів. Але слова, які відрізняються лише пере­ставленням А1, А2, А3, насправді однакові. Через те, що літери А1, А2, А3 можна переставляти 3! способами, всі 8! слів розбиваються на групи з 3! однакових. Тому різних слів всього 8!/3!.

20.  Скільки різних слів можна отримати, переставляючи літери  слова "ОРТОГОНАЛЬНИЙ"?

Розв'язок. В цьому слові три літери О та дві літери Н. Вважаючи всі літери різними, отримуємо 13! слів. Ототожнюючи слова, які відрізня­ються лише переставленням літери Н, але не О, дістанемо 13!/2! різних слів, ототожнюючи тепер слова, які відрізняються переставленням літер О, отримаємо остаточний результат 13!/(2!∙3!).    

21.  "МАТЕМАТИКА". Відповідь. 10!/(3!∙2!∙2!).

Цикл задач про слова продемонстрував одне змістовне міркуван­ня ідею кратного підрахунку. Замість підрахунку кількості об'єктів, які нас  цікавлять, іноді буває зручно перерахувати інші об'єкти, кіль­кість яких перевищує кількість вихідних в число разів, яке нам відоме. Ось ще чотири задачі, при розв'язанні яких використовується цей спосіб.

22.  В країні 20 міст, кожні два з яких з'єднані авіалінією. Скільки авіаліній в цій країні?

Розв'язок. Кожна авіалінія з'єднує два міста. За перше місто мож­на взяти будь-яке з 20 міст (місто А), за друге – будь-яке з 19, які залишилися (місто В). Перемноживши ці числа, дістаємо 20∙19 = 380. Але при цьому підрахунку кожна авіалінія врахована двічі (перший раз, коли за перше місто було вибрано місто А,  друге  – місто В, а другий раз – навпаки). Таким чином, кількість авіаліній дорівнює 380:2 = 190. 

23.  Скільки діагоналей в опуклому "n"-кутнику?

Розв'язок. За перший кінець діагоналі можна взяти будь-яку з n  вершин, а за другу – будь-яку з n – 3 вершин, відмінних від вибраної та двох сусідніх з нею (див. мал. 10). При цьому підрахунку кожна діагональ обліковується двічі. 

Відповідь. n(n - 3)/2.

24. Намисто – це кільце, на яке нанизано намистинки. На­мисто можна повертати, але не перевертати. Скільки різних намист можна зробити з 13 різнокольорових намистин (див. мал. 11)?

Розв 'язок. Уявимо собі на деякий час, що намисто не можна повер­тати. Тоді його можна зробити 13! різними способами. Але будь-яке місцезнаходження намистин та 12 варіантів, які дістаються з нього поворотами, слід вважати одним варіантом намиста.   Відповідь. 13!/13 = 12!.

25. Припустимо тепер, що намисто можна й перевертати. Скільки тоді різних намист можна зробити з 13 різнокольорових на­мистин?

Розв 'язок. Перевороти скорочують кількість намист у 2 рази.  Відповідь. 12!/2.

Наступна задача ілюструє ще одне важливе комбінаторне міркування.

26.  Скільки існує 6-цифрових чисел, в напису  яких є при­наймні одна парна цифра? Розв'язок. Замість того, щоб підраховувати кількість потрібних 6-

цифрових чисел, визначимо кількість 6-цифрових чисел, яким не при­таманна необхідна, властивість. Оскільки це точно ті самі числа, в напису яких зустрічаються тільки непарні цифри, то їх кількість, оче­видно, дорівнює 5⁶ = 15625. Всього 6-цифрових чисел 900000 Тому кількість 6-цифрових чисел, яким притаманна вказана властивість, дорівнює 900000-15625 = 884375.  

Основним моментом при розв'язуванні цієї задачі був так знаний перехід до доповнення: підрахунок "непотрібних" варіантів замість підрахунку "потрібних". Ось ще одна задача, розв'язуючи яку, кори­сно послуговуватися цим міркуванням.

Задача 27.  В абетці племені Бум-Бум шість літер. Словом є будь-яка, послідовність, з шести літер, в якій є принаймні дві однакові літери. Скільки слів в мові племені Бум-Бум?

Відповідь, 6⁶ - 6!.

Для викладачів. На закінчення хотілося б відзначити, що ідеї, яка об'єднує задачі виділеного в главі циклу, природно присвятити окреме заняття. При цьому необхідно весь час повертатися до вже пройденого матеріалу. Тому ми надаємо додатковий список задач для самостій­ного розв'язання.

Задачі для самостійного розв'язання.

Задача 28. В кіоску "Друк України" продаються 5 видів конвертів та 4 види марок. Скількома способами можна, купити конверт з маркою?

Задача 29. Скількома способами можна, вибрати голосну та приго­лосну літери зі слова "КРУЖОК"?

Задача 30. На дошці написано 7 іменників, 5 дієслів та 2 прикмет­ники. Для речення треба вибрати по одному слову кожної з цих частин мови. Скількома способами це можна зробити?

Задачі  31.  У двох колекціонерів-початківців є по 20 марок і по 10 значків.    Чесним обміном називається обмін однієї марки на одну марку або одного значка на один значок.   Скількома способами колекціонери можуть здійснити чесний обмін?

Задача 32. Скільки існує 6-цифрових чисел, всі цифри яких мають однакову парність?

Задача 33. Треба відіслати 6 термінових листів. Скількома спосо­бами це можна зробити, якщо для передачі листів можна використати трьох кур'єрів і кожен лист можна дати будь-якому з кур'єрів?

Задача 34. Скількома способами з повної колоди (52 карти) можна вибрати 4 карти різних мастей і вартості?

Задача 35. На полиці стоять 5 книг. Скількома способами можна викласти в купку декілька з них (купка може складатися і з однієї книги)?

Задача 36. Скількома способами можна поставити 8 тур на шахову дошку так, щоб вони не били одна одну?     

Задача 37. На танцмайданчику зібралися N юнаків та N дівчат. Скількома способами вони можуть розбитися на пари для участі в черговому танці?      у

Задача 38. Чемпіонат України по шахам проводиться в одне коло. Скільки грається партій, якщо участь беруть 18 шахістів?

Задача 39. Скількома способами можна поставити на шахову дошку а) дві тури; б) двох королів; в) двох слонів; г)двох коней; д) двох ферзів так, щоб вони не били одне одного?

Задача 40. У мами два яблука, три груші та чотири апельсини. Кож­ного дня протягом дев'яти днів підряд вона дає синові один з фруктів, які залишилися. Скількома способами це може бути зроблено?

Задача 41. Скількома способами можна поселити 7 студентів в З кімнати: одномісну, двомісну та чотиримісну?     

Задача 42. Скількома способами можна розставити на першій гори­зонталі шахової дошки комплект білих фігур (король, ферзь, дві тури, два слони та два коні)?

Задача 43. Скільки слів можна скласти з п'яти літер А і не більш як її трьох літер Б?

Задача 44. Скільки існує 10-цифрових чисел, в яких маємо принаймні ми однакові цифри?

Задача 45. Яких 7-цифрових чисел більше:  тих, в запису яких є  І ЧИ інших?

ВІДПОВІДІ, ВКАЗІВКИ, РОЗВ'ЯЗКИ

28. 5∙4=20     29. 2∙3=6     30. 7∙5∙2=70      31. 20∙20+ 10∙10 = 500    32. 5⁶+4∙5⁵       33. 3⁶    34. 13∙12∙11∙10

35. 5 + 5∙4 + 5∙4∙3 + 5∙3∙2 + 5∙4∙3∙2∙1 = 325     36. 8!     37. n!   38. 18∙17/2 = 153    39. а) 64∙49/2 = 1568;  б) (4∙60+24∙58 + 36∙55)/2 = 1806; в) (28∙56 +20∙54 + 12∙52 + 4∙50)/2 = 1736; г) (4∙61 + 8∙60 + 20∙59 + 16∙57 + 16∙55)/2 = 1848; д) (28∙42 + 20∙40 + 12∙38 + 4∙36)/2 = 1288.

40. 9!/2!3!4!     41. 7!/1!2!4!    42. 8!/2!2!2!    43. 1 + 6!/5! 1! + 7!/5! 2! + 8!/(5!∙3!) = 84  44. 9∙10⁹ – 9∙9!

45. 8∙9 < 9∙10⁶ – 8∙9⁶, і тому чисел а одиницею більше.   46. 6³-5³    47. 13∙11∙9∙7∙5∙3∙1   48. 9∙10^7∙5

Основні правила комбінаторики

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то A об’єднане з B містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то A перемножене з B містить m×n елементів, тобто пар.

Кількість елементів множини A будемо далі позначати |A|.

Ці правила мають також вигляд:

Принцип суми. Якщо об'єкт A можна вибрати m способами, а об'єкт B – n іншими способами, то вибір "або A, або B" можна здійснити m+n способами.

Принцип добутку. Якщо об'єкт A можна вибрати m способами і після кожного такого вибору об'єкт B може бути вибраним n способами, то вибір "A і B" в указаному порядку можна здійснити m×n способами.

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

Правило добутку застосовується для підрахунку кількості об'єктів, що розглядаються як елементи декартових добутків відповідних множин. Отже, ці об'єкти являють собою скінченні послідовності – пари, трійки тощо.

Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

Означення. Розміщення з повтореннями по m елементів n-елементної множини A – це послідовність елементів множини A, що має довжину m.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Якщо |A|=n, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина Am=A´A´…´A, містить nm елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2m. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини m.

У багатьох комбінаторних задачах об'єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A1, другий – A2, тощо. Але досить часто множина A2 визначається лише після того, як зафіксовано перший член послідовності, A3 – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A1|=10, |A2|=|A3|=…=|A7|=9, і загальна кількість номерів є 10×96.

2. Розміщення та перестановки без повторень

Означення. Розміщення по m елементів n-елементної множини A, де m£n – це послідовність елементів множини A, що має довжину m і попарно різні члени.

Приклади.

1. При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c), (b,a), (b,c), (c,a), (c,b).

2. Розподіл n різних кульок по одній на кожний з m різних ящиків, m£n. Ящики можна пронумерувати від 1 до m, кульки – від 1 до n. Тоді кожному розподілу взаємно однозначно відповідає послідовність довжини m попарно різних номерів від 1 до n.

Неважко підрахувати кількість послідовностей з прикладу 2. На першому місці може стояти будь-який із номерів 1, …, n. На другому – незалежно від того, який саме був на першому, будь-який із n-1, що залишилися. І так далі. За принципом добутку, таких послідовностей

n×(n-1)×…×(n-m+1),

або n!/(n-m)!. Цей добуток позначається або (n)m або nm.

Означення. Перестановка n елементів множини A без повторень – це розміщення по n елементів, тобто послідовність елементів множини A, що має довжину n і попарно різні члени.

Приклад. При A={a, b, c} усі перестановки –це трійки (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Очевидно, що кількість перестановок n елементів дорівнює кількості розміщень по m при m=n, тобто n!. Отже, 1·2·..·n=n!.

3. Комбінації без повторень

Означення. Комбінація по m елементів n-елементної множини – це її m-елементна підмножина.

Приклади.

1. При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b}, {a,c}, {b,c}.

2. Розподіл n різних кульок по одній на кожний з m однакових ящиків, m£n. Оскільки ящики однакові, то розподіл взаємно однозначно визначається підмножиною з m кульок, що розкладаються.

З кожної m-елементної комбінації елементів n-елементної множини можна утворити m! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є

 =. Ця кількість позначається або .

4. Перестановки з повтореннями

Означення. Перестановка з повтореннями по m елементів множини A={a1, a2, …, an} складу (k1, k2, …, kn) – це послідовність довжини m=k1+k2+…+kn, в якій елементи a1, a2, …, an повторюються відповідно k1, k2, …, kn разів.

Приклади.

1. При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Зразки задач з комбінатори для осмислення.

Задачі на круги Ейлера

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

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

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

Задача 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 не вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?

Зразки задач

Задача 1. З Києва до Чернігова можна дістатися пароплавом, поїздом, автобусом, літаком; з Чернігова до Новгород-Сіверська – пароплавом і автобусом. Cкількома способами можна здійснити подорож за маршрутом Київ – Чернігів – Новгород-Сіверськ?

Розв’язання. Очевидно, число різних шляхів з Києва до Новгород-Сіверська дорівнює 4∙2 = 8, бо, обравши один з чотирьох можливих способів подорожі від Києва до Чернігова, маємо два можливих способи подорожування від Чернігова до Новгород-Сіверська.

Такі міркування, які були проведені при розв'язуванні задачі 1, доводять справедливість такого простого тверджен­ня, яке будемо називати основним правилом комбінаторики.

Якщо деякий вибір А можна здійснити m різними спосо­бами, а для кожного з цих способів деякий другий вибір В можна здійснити n способами, то вибір А і В (у вказаному порядку) можна здійснити m∙n способами.

Інакше кажучи, якщо певну дію (наприклад, вибір шля­ху від Києва до Чернігова) можна здійснити m різними спо­собами, після чого другу дію (вибір шляху від Чернігова до Новгород-Сіверська) можна здійснити n способами, то дві дії разом (вибір шляху від Києва до Чернігова, вибір шляху від Чернігова до Новгород-Сіверська) можна здійснити m∙n способами.

Задача 2. У розиграші першості країни з футбола бере участь 16 команд. Скількома способами можуть бути розподілені золота і срібна медалі?

Розв’язання. Золоту медаль може одержати одна з 16 команд. Після того, як визначено володаря золотої медалі, срібну медаль може мати одна з 15 команд. Отже, загальне число способів, якими може бути розподілена золота і срібна медалі, до­рівнює 16∙15 = 240.

Сформулюємо тепер основне правило комбінаторики (правило множення) в загальному вигляді.

Нехай треба виконати одну за одною k дій. Якщо першу дію можна виконати n₁ способами, другу дію – n₂ способами, третю дію – n₃ способами і так до k-ї дії, яку можна вико­нати n_k способами, то всі k дії разом можуть бути виконані  n_1∙ n_2∙ n₃∙…∙ n_k-1 n_k способами.

Задача 3. Скільки чотиризначних чисел можна склас­ти з цифр 0, 1,2, 3,4, 5, якщо:

а)            жодна цифра не повторюється більше одного разу;

б)           цифри можуть повторюватись;

в)            числа повинні бути непарними?
Розв'язання.  а) Першою цифрою числа може бути одна з 5 цифр 1, 2, 3, 4, 5 (0 не може бути, бо тоді число не чотиризначне); якщо перша цифра обрана, то друга може бути обрана 5 способами, третя – 4, четверта – 3. Згідно з правилом множення загальне число способів дорівнює 5∙5∙4∙3 = 300.

б)           Першою цифрою може бути одна з цифр 1, 2, 3, 4, 5 (5 можливостей), для кожної з наступних цифр маємо 6 мож­ливостей (0, 1,2,3, 4, 5). Отже, число шуканих чисел дорів­нює 5∙6∙6∙6=5∙ 6³ = 1080.

в)            Першою цифрою може бути одна з цифр 1, 2, 3, 4, 5, а останньою – одна з цифр 1,3,5, (числа повинні бути не­парними). Отже, загальна кількість чисел дорівнює 5∙6∙6∙3 = 540.

Задача про щасливі квитки

Задача. Номер автобусного квитка складається з 6 цифр. Квиток називають щасливим, якщо сума перших трьох цифр його номера рівна сумі трьох останніх цифр. Які автобусні квитків більше: щасливих або тих, чиї номери діляться на 11?

Розв’язання. Щасливі квитки, згадані в умові, називатимемо щасливими по-київські. Назвемо квиток щасливим по-вінницьки, якщо сума цифр його номера, що стоять на парних місцях, рівна сумі цифр, що стоять на непарних місцях.

З'ясуємо спочатку, які щасливі квитків більше  по-київські або по-вінницькі? Їх порівну, оскільки між ними можна встановити взаємно однозначну відповідність таким чином. Переставимо цифри номера квитка, щасливого по-київськи: перші три цифри поставимо на непарні місця (перше, третє і п'яте), а останні три цифри  на парних (наприклад, номер 129345 перетвориться на 132495.) Отримаємо щасливий по-вінницьки квиток.

Тепер відмітимо, що номер будь-якого квитка, щасливого по-вінницьки ділиться на 11. Зворотне невірно: існують не щасливі по-вінницькі квитки, номери яких діляться на 11, наприклад, якщо різниця сум цифр, що стоять на непарних і парних місцях, рівна 11. Тому квитків з номерами, що діляться на 11 більше, ніж щасливих по-вінницьки, а значить і по-київські.

¹ Ознака подільності на 11: «Число ділиться на 11, тоді і тільки тоді, коли сума його цифр, що стоять на парних місцях, мінус сума цифр, що стоять на непарних місцях, ділиться на 11».¹ Признак делимости на 11: «Число делится на 11, тогда и только тогда, когда сумма его цифр, стоящих на чётных местах, минус сумма цифр, стоящих на нечётных местах, делится на 11».

Для того щоб добре засвоїти основне правило комбінато­рики,

обов'язково треба розв'язати подані нижче вправи.

Вправи

4. Скільки існує п’ятицифрових чисел, для запису яких використовуються тільки цифри: а) 1, 2, 3, 4  б) 0, 1, 2, 3?( Кожна цифра може бути використана декілька разів). Відповідь: а)4⁵ , б) 3∙4⁴.

5.На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються різними шляхами. Відповідь: 49 способи, 42 способи.

6.В наряд можна послати трьох чоловік, одного із п’яти офіцерів, одного із семи сержантів і одного із 20 солдат. Скількома способами можна скласти наряд?

Відповідь: 20∙7∙5.

7. а)Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5? Відповідь: 3⁵.

В наряд можна послати двох чоловік, одного із трьох сержантів і одного із 6 солдат. б)Скількома способами можна скласти наряд? Відповідь: 3∙6 =18.

8.Скільки різних дільників має число 3⁵∙5⁴? Відповідь: (5+1)∙(4+1) = 30. Скласти таблицю всіх дільників.

9. Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5, якщо кожну з цих цифр можна використовувати не більше одного разу? Відповідь: 5∙4∙3.

10. Скількома способами 7 осіб можуть розташуватись в чергу до каси? Відповідь: 7∙6∙8∙5∙4∙3∙2∙1.

11. В класі вивчають 14 предметів. В понеділок 7 уроків, причому всі
уроки різні. Скількома способами можна скласти розклад на понеділок?

12. Скільки є п'ятизначних чисел, які діляться на 5?

13. П'ять хлопчиків і 5 дівчаток сідають в ряд не 10 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити? Відповідь: (5!)∙(5!)

14. Скільки різних слів можна утворити переставлянням букв у слові «математика»? Відповідь: 10!/(3!∙2!∙2!)

15.Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 33 букви алфавіту.

16. В селищі мешкає 1500 жителів. Довести, що принаймні два з них мають однакові  ініціали.

17. Скільки різних дільників має число 6⁶∙7⁴?

18. Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5, якщо кожну з цих цифр можна використовувати не більше одного разу? Відповідь: 5∙4∙3.

Скількома способами 7 осіб можуть розташуватись в чергу до каси? Відповідь: 7∙6∙8∙5∙4∙3∙2∙1.

19. В класі вивчають 10 предметів. В понеділок 6 уроків, причому всі
уроки різні. Скількома способами можна скласти розклад на понеділок?

Скільки є п'ятизначних чисел, які діляться на 5? Відповідь: 10∙9∙8∙7∙6∙5= 151200

20. П'ять хлопчиків і 5 дівчаток сідають в ряд не 10 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити? Відповідь: (5!)∙(5!)

21. Скільки різних слів можна утворити переставлянням букв у слові «арифметика»?

22. Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 30 букви алфавіту.

23. Скільки різних дільників має число 8³∙9⁴? Скласти таблицю всіх дільників цього числа.

24. Від А до В 999 км. Вздовж дороги стоять стовпи, на яких вказано відстані до А і до В | 0.999 | ; | 1.998| ; | 2.997] ; . . . ; | 999.0 |. Скільки серед них таких, на яких є тільки дві різні цифри? Відповідь: 40.

25. Пасажир залишив речі в автоматичній камері схову, а коли при­йшов одержувати речі, то виявилось, що він забув номер. Він лише па­м'ятає, що в номері були цифри 23 і 37. Щоб відкрити камеру, треба пра­вильно набрати п'ятизначний номер. Яку найбільшу кількість номерів треба перебрати, щоб відкрити камеру?

25. В прямокутній таблиці з m рядків і n стовпців записані числа +1 і -1 так, що добуток чисел в кожному рядку і кожному стовпці дорівнює 1. Скількома способами це можна зробити?

Відповідь: Всі таблиці, які мають вказану в умові задачі властивість, можна скласти так. Всюди, крім останнього рядка і останнього стовпця, до­вільно виписуємо +1 і –1. Це можна зробити 2^(n-1)(m-1) способами. Нехай р – добуток всіх виписаних чисел. Тепер в кожному з перших m -1  рядів на перетині з n-м стовпцем виписуємо +1 або –1 так, щоб добуток чисел в усьому рядку дорівнював 1. Позначимо добуток чисел, які будуть виписані в n-му рядку, через x. Тепер в кожному з перших n-1 стовпців на перетині з m-м рядком випишемо теж +1 або –1 тaк, щоб добуток в стовпці дорівнював 1. Добуток чисел, які будуть виписані в m-му рядку, позначимо через у. Зауважимо, що х і у мають однаковий знак. Справді, рх = 1, ру = 1. і тому р²ху = 1, і, значить, ху > 0. Випишемо на перетині т-го рядка і л-го стовпця 1 з тим знаком, який мають х і у. Тоді добуток чисел в n-му стовпці і m-му рядку також до­рівнюватиме 1. Склали таблицю, яка має вказану властивість. Число всіх  таких   таблиць   дорівнює  2^(n-1)(m-1).

26. На залізниці є десять семафорів, кожний з яких може передати три сигнали: червоний, жовтий, зелений. Скільки різних сигналів можна передати за допомогою усіх семафорів. Відповідь: 3^10.

27. Існує десять ліхтариків, кожен з яких може бути або включений, або виключений.Скільки різних сигналів можна передати за допомогою усіх ліхтарів? Відповідь: 2¹⁰.

28. Проста шашка знаходиться в крайньому нижньому лівому полі шахової дошки. Скількома різними способами вона може  пройти в дамки? Способи вважаються різними, якщо вони відміняються один від одного хоча б одним ходом.

Відповідь: На другу горизонталь шашка може перейти одним способом, на третю – двома, на четверту – трьома, на п’яту – шістьма, на шосту – дев’ятьма, на сьому горизонталь – двадцятьма способами, а пройти в дамки шашка може 35 способами.

29. У квадраті 3х3 клітинки верхня ліва точка позначена літерою А. Скільки можна побудувати трикутників, одною з вершин яких є точка А, а дві інші вершини – будь-які вершини квадратиків 1х1 даного квадрата? Відповідь: 25 трикутників.