Комбінаторика, її мета і задачі. Правила суми і добутку

Конспект уроку 

Відео-урок з математики:

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

Урок 2. Комбінаторика. Перестановки.

Урок 3. Розміщення та комбінації

Задача 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.

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

Вправи

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 трикутників.

Задачі комбінаторики на правило добутку.

1.  Скількома способами можна вибрати голос­ну і приголосну зі слова «паркет»?

 2. а)Скількома способами можна вказати на ша­ховій дошці два квадрати – білий та чорний?

     б) Розв'яжіть цю задачу, якщо немає обмежень на колір квадрата.

    в) Розв'яжіть її, якщо потрібно вибрати два білих квадрати.

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

4. З 3 примірників підручника алгебри, 7 при­мірників підручника геометрії та 6 примірників підручни­ка фізики потрібно вибрати комплект, що містить по одно­му підручнику з кожного предмету. Скількома способами це можна зробити?

5. У кошику 12 яблук та 10 апельсинів. Іван­ко вибирає або яблуко, або апельсин, після чого Надійка вибирає з фруктів, що залишилися, і яблуко, і апельсин.  Скільки можливостей таких виборів?  За якого вибору Іван­ка Надійка має більше можливостей вибору?

6. Скількома способами можна обтягнути 6 стільців тканиною, якщо є тканина шести різних коль­орів, і всі стільці повинні бути різнобарвними?

7 . Скількома способами можуть розташувати­ся у турнірній таблиці 10 футбольних команд, якщо відо­мо, що ніякі дві команди не набрали порівну очок?

8. Скільки чотиризначних чисел можна утво­рити з цифр 0, 1,2, 3, не повторюючи їх?

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

10. Є 8 токарів.  Скількома способами можна поручити трьом із них виготовлення трьох різних деталей по одному виду на кожного.

11.  До профкому обрано 9 чоловік. З них треба обрати голову, його заступника, секретаря та культорга. кількома способами це можна зробити?

Відповідь: n =9∙8∙7∙6 =  3024.

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

13. На зборах мають виступити 5 чоловік: А, Б, В, Г, Д. Скількома способами можна їх розташувати у список промовців, якщо:

1)      Б не повинен виступати перед А;

2)      якщо Б мусить виступити відразу за А?

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

Комбінаторика, її мета і задачі. Правила суми і добутку

     Мета: ознайомити учнів з новим розділом математики; навчати практичному застосуванню набутих знань; розвивати увагу й пам'ять; виховувати зацікавленість предметом.

     Тип уроку: урок формування нових знань.

     Обладнання: таблиця «Вибір правила», роздавальний матеріал (картки з буквами і цифрами для розв'язування задач).

ХІД УРОКУ

I. Організаційна частина

II. Оголошення теми і мети уроку

     Сьогодні ми познайомимося з новим розділом математики, який дещо відрізняється від тих, які вивчались раніше. Назвіть розділи математики, які вам відомі.

     (Учні називають: алгебра, геометрія, тригонометрія.)

     Розділ математики, який ми починаємо вивчати, називається комбінаторикою.

ІІІ. Вивчення нового матеріалу

1. Розповідь учителя

     Комбінаторикою називається розділ математики, в якому вивчаються питання про те, скільки різних сполук, що відповідають тим чи іншим умовам, можна скласти із заданих об'єктів (елементів множини). Часто доводиться розв'язувати задачі, в яких потрібно вибирати з даної кількості елементів такі, що мають певні властивості, або розміщувати їх у певному порядку.

     Наприклад, скільки пар чергових можна утворити з 34 учнів класу? Скількома способами можна розмістити 7 гостей за столом? Скільки існує шестицифрових телефонних номерів?

     Задачі такого виду називаються комбінаторними і розв'язуванням таких задач ми й будемо займатись.

2. Завдання для учнів

     Спробуйте з'ясувати, скільки різних «слів» можна скласти з букв о, т, р, якщо «словом» вважати будь-яке поєднання цих букв? (6 «слів».)

     На це запитання відповісти неважко, адже букв усього три! А якщо елементів у множині буде більше? Щоб можна було розв'язувати комбінаторні задачі різних видів, ознайомимося з основними комбінаторними правилами: правилом суми і правилом добутку.

3. Задача

     У класі 34 учня, серед яких 16 хлопців і 18 дівчат.

1) Скількома способами можна вибрати одного учня цього класу?

2) Скількома способами двох учнів — хлопчика й дівчинку?

3) Скількома способами можна вибрати дівчинку?

4) Уже вибрано одного учня. Скількома способами можна вибрати після цього хлопчика й дівчинку?

     (На дошку вивішується (проектується) таблиця «Вибір правила».)

Розв'язання задачі

1) Хлопчика можна вибрати 16 способами, а дівчинку — 18 способами, тоді за правилом суми або дівчинку, або хлопчика можна вибрати

16+18=34 (способами).

2) За правилом добутку і дівчинку, і хлопчика можна вибрати

16∙18=288 (способами).

3) Дівчинку можна вибрати 18 способами.

4) Якщо один учень уже вибраний, то можливі два варіанти:

     а) якщо була обрана дівчинка, тоді дівчат залишилось 17, отже дівчинку можна вибрати 17 способами, а хлопчика — 16, а пару можна вибрати

17∙16=272 (способами).

     б) якщо був обраний хлопчик, то їх залишилось 15, отже існує 15 способів вибору хлопчика, для дівчинки — 18 способів, для пари —

15∙18=270 (способів).

     За правилом суми маємо

272+270=542 (варіанти).

Відповідь. 1) 34; 2) 288; 3) 18; 4) 542.

IV. Розв'язування вправ

1. Скількома способами можна вибрати 1 фрукт, якщо на тарілці лежить 8 яблук і 6 груш?

(14.)

2. В їдальні є 4 перших і 6 других блюд. Скількома способами можна скласти обід?

(24.)

3. Скільки можна утворити двоцифрових чисел із цифр 0, 1,2, 3, 4, 5, 6, 7, 8, 9, якщо цифри в запису числа не повторюються?

(90.)

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

(5∙5∙5=125; 5∙4∙3=60.)

5. У продажу є 5 ручок, 4 олівці та 8 лінійок різних видів. Скількома способами учень може придбати набір з ручки, олівця та лінійки?

(160.)

Творче завдання

     Учням пропонується самостійно сформулювати схожі задачі і представити їх учням класу для розв'язування.

Робота з підручником

     Ознайомитися з теоретичним матеріалом у підручнику.

V. Підсумок уроку

1. Які задачі називають комбінаторними?

2. Який розділ математики називають комбінаторикою?

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

4. Сформулюйте правила суми і добутку. Коли вони застосовуються?

VI. Домашнє завдання

1.     Вивчити правила з підручника (розділ XII § 3).

2.     Розв'язати задачі.

1. На будівництві працює 5 мулярів, 4 теслі та 2 штукатури. Скількома способами можна вибрати одного муляра? Одного теслю? Одного штукатура? Бригаду, в якій буде працювати по одному з робітників кожної професії?

2. Скільки п'ятицифрових чисел можна скласти з цифр 2,4, 5, 8, 9, якщо цифри в запису числа не можуть повторюватися? Якщо будуть повторюватися?