Методи розв’язання комбінаторних задач

Зміст

Вступ……………………………………………………………………………………………3

Основні теоретичні відомості……………………………………………………4

Приклади розв’язання типових задач……………………………………16

Вправи до самостійної роботи…………………………………………………22

Підготовка до ЗНО……………………………………………………………………24

Питання для перевірки теоретичних знань…………………………26

Вступ

Розділ математики, у якому вивчається питання про те, скільки різних конфігурацій, які задовольняють тим або іншим умовам, можна скласти з заданих об’єктів, називають комбінаторикою.

У повсякденному житті нерідко виникають проблеми, які мають не один, а декілька варіантів розв’язання. Щоб зробити правильний вибір, дуже важливо не упустити ні один з них. Для цього треба вміти здійснювати перебір всіх можливих варіантів або хоча б підраховувати їх число. Такого роду задачі називають комбінаторними.

Комбінаторика – важливий розділ математики, знання якого необхідно представникам різноманітних спеціальностей.

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

У даних методичних рекомендаціях розглянуті різні методи розв’язання комбінаторних задач. Насамперед пропонується освоїти метод розв’язання комбінаторних задач, заснований на застосуванні правил суми та добутку. Цей метод дозволяє вирішувати різноманітні комбінаторні задачі, практично не вдаючись до використання формул. Він дає можливість оволодіти основними комбінаторні ідеями.

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

Основне застосування комбінаторики пов’язано з розв’язанням ймовірнісних задач, що приводять до класичної ймовірнісної моделі.

Вправи до самостійної роботи

1. У букеті 10 троянд і 12 хризантем. Скількома способами можна вибрати із букета: а) або одну троянду, або одну хризантему; б) одну троянду або одну хризантему; в) одну троянду й одну хризантему?

2. У магазині посуду є 5 видів чашок і 7 видів блюдець. Скількома способами можна вибрати пару блюдець і чашку?
3. У магазині посуду із задачі 2 є ще 6 видів чайних ложок. Скільки існує способів скласти набір із чашки, блюдця і ложки?
4. У глядацькому залі кінотеатру всього 6 дверей. Скільки існує способів: а) увійти до глядацького залу і вийти з нього; б) увійти до залу і вийти, але так, щоб вхід і вихід здійснювалися через різні двері
5. У глядацькому залі із задачі 4 існує ще двоє дверей до кімнати кіномеханіка. Скількома способами кіномеханік може потрапити на робоче місце?
6. У класі 30 учнів. Щодня призначається один черговий. Скількома способами можна скласти графік чергування на 5 днів так, щоб ніхто не чергував більше одного разу?
7. Скільки існує різних телефонних номерів, якщо вважати, що кожний номер складається із 7 цифр (телефонний номер може починатися з нуля)? Як зміниться розв’язок задачі, якщо телефонні номери можуть бути як семи-, так і шестицифровими?
8. Кидають дві монети. Скільки різних варіантів випадання «орел – решка» може при цьому вийти?
9. Гральний кубик кидають тричі. Скільки різних послідовностей чисел може при цьому вийти?
10. Кожна літера азбуки Морзе — це послідовність крапок і тире. Скільки різних слів можна скласти, якщо використовувати для кожного з них: а) 5 символів; б) не більше ніж 5 символів?
11. Скількома способами можна вказати на шахівниці: а) два білих квадрати; б) білий і чорний квадрати, якщо вони не лежать на одній горизонталі або одній вертикалі?
12. У кошику 10 яблук і 12 апельсинів. Іван вибирає або яблуко, або апельсин, після чого Надя вибирає із фруктів, що залишилися, апельсин. Скільки можливостей такого вибору?
13. Скільки можна скласти із цифр 0, 1, 2, 3, 4, 5: а) різних трицифрових чисел; б) різних трицифрових чисел, якщо цифри в них не повторюються; в) різних трицифрових чисел, що діляться на 5?
14. Чотири учні одержують оцінки 2, 3, 4, 5. а) Скількома способами можна поставити їм оцінки? б) Скількома способами можна поставити оцінки так, щоб жодні два учні не одержали однакових? в) Скількома способами можна поставити оцінки так, щоб усі одержали 4 або 5?
15. У команді 12 членів. Скількома способами можна вибрати в ній капітана і воротаря?
16. Скільки словників треба видати, щоб можна було безпосередньо виконувати переклади з кожної із п’яти мов: російської, англійської, французької, німецької та іспанської на будь – яку іншу з цих мов?
17. Розклад одного дня містить 5 уроків. Визначте кількість таких розкладів при виборі з 11 предметів і за умови, що один предмет займає один урок. Як зміниться розв’язування задачі, якщо відомо, що першим уроком обов’язково має бути математика?
18. Скількома способами можна вибрати з повної колоди карт (52 шт.) по одній карті кожної масті за умови, що серед вийнятих карт немає жодної пари однакових, тобто двох королів, двох дам і т. д.?
19. Скільки різних дробів, що не дорівнюють одиниці, можна скласти з чисел 3, 5, 7, 11, 13, 17, 19, 23 так, щоб до кожного дробу входило два числа? Скільки серед них буде правильних?
20. Чотири біатлоністи з України брали участь у чемпіонаті світу. Скількома способами могли бути розподілені місця, які посіли представники України, якщо: а) жоден із них не посів місце нижче п’ятнадцятого, і жодне місце не було поділено; б) жоден із них не посів призового місця, а всього було 15 учасників чемпіонату?
21. Скільки різних чотирицифрових натуральних чисел можна скласти із цифр: а) 2, 3, 5, 7, 9; б) 0, 2, 3, 5, 7, 9?
22. Скільки різних чотирицифрових парних чисел можна скласти із цифр: а) 1, 3, 5, 7, 8; б) 2, 4, 6, 8, 9?
23. Людина має 10 друзів і протягом декількох днів запрошує двох із них у гості так, що кожен побував у неї в гостях тільки один раз. Скільки різних варіантів зустрічей вона може скласти?
24. Людина має 10 друзів і щодня запрошує декількох із них у гості (або одного), але в різний час. Скільки варіантів прийому гостей вона може скласти, якщо жодні групи гостей не повторюються?
25. Скільки різних натуральних чисел можна скласти із цифр 1, 2, 3, 4?
26. Двох братів привели у Будинок дитячої творчості, де працює 5 різних гуртків. Скільки є варіантів для зарахування хлопців до гуртків, якщо кожен хлопчик може відвідувати тільки один гурток?
27. Номери трамвайних маршрутів колись позначали двома кольоровими ліхтарями. Яку кількість різних маршрутів можна позначити, якщо використовувати ліхтарі шести кольорів?
28. Два листоноші повинні рознести 8 листів за вісьмома адресами. Скількома способами вони можуть розподілити цю роботу?
29. Поїзд метро робить 10 зупинок, не враховуючи початкової, під час яких виходять усі пасажири і не заходять нові. Скількома способами можуть бути розподілені між цими зупинками 200 пасажирів, які ввійшли у поїзд на початковій зупинці?
30. Номер автомобільного причепа складається із двох букв і чотирьох цифр. Скільки різних номерів можна скласти, використовуючи 20 букв і 10 цифр?
31. Трамвайні маршрути позначають одним, двома або трьома кольоровими ліхтарями. Яку кількість різних маршрутів можна скласти, якщо використовувати ліхтарі шести кольорів?
32. Є 6 різних троянд і 3 різні гілки папороті. Скільки існує варіантів вибору квітів за умови, що у виборі беруть участь і троянди, і папороть? (Слід врахувати, що одна троянда й одна папороть обов’язково мають бути обрані.) Як зміниться розв’язування задачі, якщо додасться 5 різних ромашок, які також будуть брати участь у виборі?
33. Четверо юнаків і дві дівчини вибирають спортивну секцію. Секцію хокею і боксу – тільки юнаки, художньої гімнастики – тільки дівчата, а гандбол і баскетбол – і юнаки, і дівчата. Скількома способами можуть розподілитися між секціями ці шість осіб?
34. У шаховій зустрічі беруть участь дві команди по 8 членів у кожній. Кожна пара суперників і колір фігур визначаються жеребкуванням. Яка кількість різних результатів жеребкування?
35. Скількома способами можна розставити 10 людей у шеренгу?
36. Скільки трицифрових чисел можна скласти із чисел:                            а) 3, 5, 7;                       б) 3, 5, 0?
37.  Скільки перестановок можна скласти із літер слова «привіт»?
38. Скількома способами можуть розподілитися місця між: а) десятьма футбольними командами; б) десятьма футбольними командами, якщо «Динамо» і «Шахтар» зайняли перші два місця?
39. Скількома способами можна розставити 5 книг з алгебри і 3 книги з геометрії так, щоб усі книги з одного предмету: а) стояли поруч; б) не стояли поруч?
40. Скількома способами можна розставити книги з математики і фізики так, щоб жодні дві книги з одного предмету не стояли поруч, якщо: а) з фізики — 5 книг, з математики — 5; б) з фізики — 5 книг, з математики — 4?
41. У купе залізничного вагона є два протилежних дивани по 5 місць у кожному. Із 10 пасажирів четверо бажають сидіти обличчям до паровоза, троє – спиною до паровоза, а решті байдуже, як сидіти. Скількома способами можуть розміститися пасажири?
42. Скількома способами групу з восьми осіб можна розсадити за круглим столом?
43. На зборах мають виступати 5 осіб А, Б, В, Г та Д. Скількома способами їх можна розподілити в списку виступаючих, якщо:   а) А виступає безпосередньо перед Б, але не першим;  б) Б повинен виступити до того, як виступить А?
44. Знайдіть кількість різних чотирицифрових чисел, які можна одержати при перестановці цифр 2, 2, 4, 4.
45. Скільки різних «слів» можна утворити перестановкою букв слова: а) «змея»; б) «змеелов»; в) «заземление»?
46. Скільки шестицифрових чисел можна скласти із двох «п’ятірок» і чотирьох «сімок»?
47. Скількома способами можна розставити 28 предметів на 4 різних підставках так, щоб: а) на кожній підставці було по 7 предметів; б) довільним чином (кожна підставка може вмістити всі 28 предметів)?
48. Скількома способами можна надіти 5 різних кілець на пальці однієї руки, крім великого пальця?
49. Скількома способами можна розставити білі фігури (2 коня, 2 слона, 2 тури, ферзя і короля) на першій лінії шахівниці?
50. Скількома способами можна вибрати трьох чергових із класу, в якому навчається 20 учнів?
51. Скільки можна побудувати трикутників, якщо за їхню вершину брати вершини правильного 12-кутника?
52. Скількома способами можна вибрати з 15 різних слів набір, що складається не більше ніж із 5 слів (зміст не важливий)?
53. У мами 2 яблука і 3 груші. Щодня протягом п’яти днів поспіль вона видає по одному фрукту. Скількома способами це може бути зроблено?
54. Як зміниться розв’язання попередньої задачі, якщо до існуючих фруктів додати 4 банани?
55. П’ятеро друзів при святкуванні Нового року завжди обмінюються поцілунками і подарунками. а) Скільки поцілунків ви зможете нарахувати? б) Скільки подарунків необхідно для святкування Нового року?
56. У класі навчаються 14 хлопчиків і 10 дівчаток. Для привітання гостей необхідно вибрати чотирьох хлопчиків і трьох дівчаток. Скількома способами це можна зробити?
57. Скількома способами можна: а) розбити 15 осіб на три команди по 5 осіб у кожній; б) вибрати з 15 осіб дві команди по 5 осіб?
58. Як зміниться розв’язання задачі 7, якщо необхідно вибрати трьох учнів для привітання, серед яких буде: а) хоча б одна дівчинка; б) представники обох статей?
59. В одного учня є 7 книг з історії культури, а в іншого – 5 книг з філософії. Скількома способами вони можуть обміняти дві книги одного на дві книги іншого?
60. Є колода із 36 карт. Скількома способами можна витягнути 8 карт так, щоб: а) було рівно два тузи; б) було хоча б два тузи; в) не було жодного туза, жодного короля; г) були туз і король різних мастей?
61. У лотереї «6 із 49» головний приз дістанеться тому, хто вгадав усі шість номерів. Менший виграш одержать ті, хто вгадав 5, 4 або 3 номера. Скільки може бути різних карток, де вгадані: а) усі 6 номерів; б) 4 номери; в) хоча б 4 номери?
62. Людина має 10 друзів і протягом декількох днів запрошує: а) трьох із них; б) деяких із них так, що компанія жодного разу не повторюється. Скільки днів вона може так робити?
63. Скільки різних дільників має число 510?
64. Для премій з математичної олімпіади виділено три примірники однієї книги, два примірники другої і один примірник третьої. Скількома способами можуть бути вручені премії, якщо в олімпіаді брало участь 20 чоловік і нікому не дають два примірники однієї книги, але можуть бути вручені дві або три різні книги?

Підготовка до ЗНО

Виконати тестові завдання за наступними посиланнями:

https://www.classtime.com/code/7ERQ3P

https://www.classtime.com/code/89E8V9

https://www.classtime.com/code/W2V5JE

Питання для перевірки теоретичних знань

1. Які задачі називають комбінаторними?
2. Що таке комбінаторика?
3. Сформулюйте і поясніть на прикладах правило суми для розв’язування комбінаторних задач.
4. Сформулюйте і поясніть на прикладах правило добутку для розв’язування комбінаторних задач.
5. Поясніть, яка скінченна множина вважається впорядкованою. Наведіть приклади впорядкованих скінченних множин.
6. Що таке факторіал? Як його позначають?
7. Поясніть, що називається розміщенням з елементів по  без повторень. Наведіть приклади.
8. Поясніть, що називається розміщенням з елементів по  з повтореннями. Наведіть приклади.
9. Запишіть формулу для обчислення числа розміщень з елементів по  без повторень. Наведіть приклади її використання.
10. Запишіть формулу для обчислення числа розміщень з елементів по  з повтореннями. Наведіть приклади її використання.
11. Обґрунтуйте формулу для обчислення числа розміщень з елементів по  без повторень.
12. Поясніть, що називається перестановкою з елементів (без повторень). Наведіть приклади.
13. Поясніть, що називається перестановкою з елементів (з повтореннями). Наведіть приклади.
14. Запишіть формулу для обчислення числа перестановок з елементів без повторень. Наведіть приклади її використання.
15. Запишіть формулу для обчислення числа перестановок з елементів з повтореннями. Наведіть приклади її використання.
16. Обґрунтуйте формулу для обчислення числа перестановок з елементів без повторень.
17. Поясніть, що називається комбінаціями з елементів по  без повторень. Наведіть приклади.
18. Поясніть, що називається комбінаціями з елементів по  з повтореннями. Наведіть приклади.
19. Запишіть формулу для обчислення числа комбінацій з елементів по без повторень. Наведіть приклади її використання.
20. Запишіть формулу для обчислення числа комбінацій з елементів по з повтореннями. Наведіть приклади її використання.
21. Обґрунтуйте формулу для обчислення числа комбінацій з  елементів по  без повторень.