15.11.2021-21.11.2021 Зразки задач комбінаторики.

  

15.11.2021-21.11.2021

Тема: Розв'язання компетентнісних завдань засобами Scratch

Теоретична частина

Створення математичної моделі до алгоритму з числовими даними

                

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

 

Задача 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 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються різними шляхами. Відповідь: Якщо довільними шляхами буде підйом і спуск, то 7*7=49 способи,  в протилежному випадку 7*6=42 способи.

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

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

 

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

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

8.Скільки різних дільників має число 3⁵∙7⁴? Відповідь: (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 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок? Відповідь:  14*13*12*11*10*9*8

12. Скільки є п'ятицифрових чисел, які діляться на 5? Відповідь: 9*10*10*10*2

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

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

15. Скільки різних слів можна утворити переставлянням букв у слові «інформатика»? Відповідь: 11!/(2!)= 19 958 400 слів

 

Практична частина

Результати виконання практичної частини надіслати у вигляді скріншотів створених веб-сторінок  на електронну адресу: vinnser@gmail.com

**************************

Додаткові завдання на розвиток кмітливості