Відео-урок з математики:
Урок 1. Основні
правила комбінаторики
Урок 2. Комбінаторика.
Перестановки.
Урок 3. Розміщення
та комбінації
Приклади комбінаторних перестановок
Перестановки на трьох елементах:
1.
123
2.
132
3.
213
4.
231
5.
321
6.
312
Перестановки на чотирьох елементах:
1.
1234
2.
1243
3.
1324
4.
1342
5.
1432
6.
1423
7.
2134
8.
2143
9.
2314
10.
2341
11.
2431
12.
2413
13.
3214
14.
3241
15.
3124
16.
3142
17.
3412
18.
3421
19.
4231
20.
4213
21.
4321
22.
4312
23.
4132
24.
4123
Перестановки на п’яти елементах:
1.
12345
2.
12354
3.
12435
4.
12453
5.
12543
6.
12534
7.
13245
8.
13254
9.
13425
10.
13452
11.
13542
12.
13524
13.
14325
14.
14352
15.
14235
16.
14253
17.
14523
18.
14532
19.
15342
20.
15324
21.
15432
22.
15423
23.
15243
24.
15234
25.
21345
26.
21354
27.
21435
28.
21453
29.
21543
30.
21534
31.
23145
32.
23154
33.
23415
34.
23451
35.
23541
36.
23514
37.
24315
38.
24351
39.
24135
40.
24153
41.
24513
42.
24531
43.
25341
44.
25314
45.
25431
46.
25413
47.
25143
48.
25134
49.
32145
50.
32154
51.
32415
52.
32451
53.
32541
54.
32514
55.
31245
56.
31254
57.
31425
58.
31452
59.
31542
60.
31524
61.
34125
62.
34152
63.
34215
64.
34251
65.
34521
66.
34512
67.
35142
68.
35124
69.
35412
70.
35421
71.
35241
72.
35214
73.
42315
74.
42351
75.
42135
76.
42153
77.
42513
78.
42531
79.
43215
80.
43251
81.
43125
82.
43152
83.
43512
84.
43521
85.
41325
86.
41352
87.
41235
88.
41253
89.
41523
90.
41532
91.
45312
92.
45321
93.
45132
94.
45123
95.
45213
96.
45231
97.
52341
98.
52314
99.
52431
100.
52413
101.
52143
102.
52134
103.
53241
104.
53214
105.
53421
106.
53412
107.
53142
108.
53124
109.
54321
110.
54312
111.
54231
112.
54213
113.
54123
114.
54132
115.
51342
116.
51324
117.
51432
118.
51423
119.
51243
120. 51234
120. 51234
Задачі комбінаторики. Правило добутку.
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, якщо кожне число містить кожну з даних цифр не
більше одного разу?
Задачі на круги Ейлера
Дуже важливими для практичних задач є формули підрахунку кількості різних елементів у
декількох множинах, що містять спільні елементи, тобто кількості елементів в об’єднанні двох
або трьох множин.
Кількість елементів об'єднання п(АÈВ) будь-яких двох скінченних множин А і В
обчислюється за формулою:
п(АÈВ) = п(А) + п(В)
- п(АÇВ).
Для будь-якої трійки скінченних множин А1, А2, А3 має місце формула кількості
елементів множини п(A1 È А2 ÈА3) , що є об’єднанням трьох множин, тобто A1 È А2 ÈА3:
п(A1 È А2 ÈА3) = п(А1)
+ п(А2) + п(А3)
- п(А1ÇА2)
- п(А1 ÇА3)
- п(А2 ÇА3) + п(А1ÇА2 ÇА3).
Наводимо
приклад використання поданих вище формул.
Задача . У лабораторії науково-дослідного
інституту працює декілька чоловік, причому кожний з них знає хоча б одну
іноземну мову, 6 чоловік знають англійську, 6 ‒ німецьку, 7 ‒ французьку, 4
знають англійську і німецьку, 3 ‒ німецьку і французьку, 2 ‒французьку і
англійську, один чоловік знає всі три мови. Скільки чоловік працює в
лабораторії? Скільки з них знає лише англійську мову? Скільки чоловік знає лише
одну мову?
Розв'язання.
Позначимо п(А), п(Н), п(Ф) кількість
співробітників у лабораторії, які знають англійську, німецьку та французьку мови
відповідно, а п(НÇФ), п(АÇН), п(АÇФ), п(АÇНÇФ) ‒ кількість чоловік, що знають по дві і три
мови відповідно. Тоді, за правилом суми, загальне число співробітників у
лабораторії дорівнює
m = п(А)+ п(Н) + п(Ф) - п(НÇФ) - п(АÇН) - п(АÇФ) + п(АÇНÇФ) = 6 + 6
+ 7 - 3 - 4 - 2
+ 1 = 11.
Тільки англійську та німецьку
мови знають
пАН = п(А ÇН) ‒ п(АÇН ÇФ) = 4-1= 3 чоловіка, тільки англійську і французьку
пАФ = п(АÇФ) - п( АÇН ÇФ) = 2-1= 1 чоловік. Тоді тільки англійську
мову знає
пА = п(А) - пАН – пАФ - п( АÇН ÇФ) = 6-3 -1-1 =1 чоловік. Тільки німецьку і французьку знають
пНФ = п(Н ÇФ) - п(АÇНÇФ) = 3 ‒ 1 = 2 чоловіки. Тоді більше однієї мови
знають
k = п(АÇНÇФ) + пАН + пАФ
+ пНФ = 1 +3+1+2 =7 чоловік, її тільки одну мову p = п - т = 11- 7 = 4 чоловіка.
Наводимо
приклади задач на використання поданих вище формул для самостійного опрацювання.
Задача 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 не
вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?
Метод
математичної індукції
Метод
математичної індукції
еквівалентний такій аксіомі:
в довільній непорожній множині натуральних чисел є найменше.
Задача. Доведіть, що
будь-яку суму в копійках, починаючи з 8 копійок можна розміняти за допомогою
двох номіналів в 3 коп та 5 коп.
Доведення.
Індукцію введемо по числу копійок. База індукції це сума в 8 коп. Очевидно її можна сплатити
отак:
3+5 = 8.
3+3+3
= 9.
5+5 =
10.
Тоді,
якщо натуральне число 3 додавати до усіх
трьох виразів, можна отримати наступні
три послідовні натуральні числа, більше 8, тобто
(3+5) + 3 = 11.
(3+3+3) + 3 = 12.
(5+5) + 3 = 13.
І так
далі …
Тому
можна записати три послідовні натуральні числа таким чином:
(3+5) + 3n = 8 + 3n.
(3+3+3) + 3n = 9 + 3n.
(5+5) + 3n = 10 + 3n.
Тут n – довільне
натуральне число.
Можна
застосувати такі індуктивні міркування. Припустимо, що нам вдалося сплатити
суму в п копійок вказаними монетами. Отже серед монет вже є по 5 коп. або по 3 коп.
Якщо серед них є монета в 5 коп., то замінимо її на дві монети по 3 коп.
і одержимо суму, що виражена наступним числом п + 1 = р + 5 +1 = р +3+3). Якщо ж всі монети суми по 3коп., то
їх не менше трьох і замінивши три монети по 3 коп.
на дві монети по 5 коп., ми також збільшимо
суму
на 1 тобто п + 1 = р + 3 +3 +3 +1
= р +5+5.
Метод математичної індукції
Індукцією називається умовивід,
у якому на основі знання частини предметів класу робиться висновок про всі
предмети класу, про клас в цілому. Індукція – це умовивід від часткового до
загального. Термін “індукція” походить від латинського слова inductio, що
означає “наведення”.
Повною індукцією називається
умовивід, у якому загальний висновок про клас предметів робиться на основі
вивчення всіх предметів цього класу.
Неповною індукцією називається умовивід, у якому загальний висновок виводиться із засновків, котрі не охоплюють усіх предметів класу.
Індукція через
простий перелік – це такий умовивід, у якому загальний висновок про клас
предметів робиться на тій підставі, щоб серед спостережуваних фактів не
траплялося жодного, який би суперечив узагальненню.
Дедуктивним (від латинського
слова deductio – виведення) називається умовивід, у якому висновок про окремий
предмет класу робиться на підставі класу
в цілому.
У дедуктивному
умовиводі думка рухається
від загального до окремого, одиничного, тому дедукцію звичайно визначають як
умовивід від загального до часткового.
Щоб дійти дедуктивного висновку, необхідно мати подвійне
знання, засновки:
1) засновок, що
має загальне положення або правило, під яке підводиться частковий випадок; 2)
засновок, у якому ідеться про той окремий предмет або частковий випадок, який
підводиться під загальне положення.
Дуже важливу роль в комбінаторіці відіграє індуктивний
метод обгрунтування правил-алгоритмів та формул.
Задача. Довести, що на площині n прямих, серед яких жодні три не перетинаються в одній точці, а
жодні дві не паралельні, поділяють площину на 1 + 0,5n(n + 1) частин.
Доведення
(методом математичної індукції):
1)Одна пряма ділить площину на 2 = 1+0,5 ∙ 1 ∙(1 +1) частини, тобто твердження справджується для формули, якщо n = 1.
Можна за
допомогою малюнків впевнитися, що формула вірна і для двох або для трьох
прямих.
2)Припустимо, що n прямих ділять площину на 1 + 0,5n(n+1)
частин. Нова (n + 1)-а пряма перетне
наявні n прямих у n точках,
що поділять нову пряму на (n + 1) частин. Отже, з наявних
1 + 0,5n(n + 1) частин площини буде перетнуто і поділено новою
прямою (n+1). Таким чином, при проведенні цієї прямої кількість частин, на які поділяється площина, зросте на (n + 1) і
дорівнюватиме:
що поділять нову пряму на (n + 1) частин. Отже, з наявних
1 + 0,5n(n + 1) частин площини буде перетнуто і поділено новою
прямою (n+1). Таким чином, при проведенні цієї прямої кількість частин, на які поділяється площина, зросте на (n + 1) і
дорівнюватиме:
1 + 0,5n(n + 1)
+ (n + 1)
= 1 + 0,5(n +
1)(n +
2).
Заняття 2. КОМБІНАТОРИКА
Скількома
способами можна проїхати з міста А в місто В? Скільки різних слів в мові
Мумбо-Юмбо? Скільки існує "симпатичних" чотирицифрових чисел? ...
Скільки ... ? Такі та деякі інші, схожі на них, питання будуть обговорюватися в
цій главі.
Почнемо
з декількох простих задач.
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.
Зауваження.
В цій задачі розв'язок має вигляд mn.
До такого розв'язку приводять задачі, в котрих на кожному з n місць може бути поставлений
елемент з деякої m-елементної множини. Ці задачі часто спричиняють труднощі у
школярів, які не завжди розуміють, яке з
чисел є основою степеня, а яке показник.
Запропонуємо
ще чотири подібні задачі.
7. Монету
кидають тричі. Скільки різних
послідовностей орлів та решок можна при цьому отримати? Відповідь: 23=8.
8. Кожну клітинку квадратної таблиці 2x2 можна
пофарбувати в чорний або білий колір. Скільки існує різних роафарбувань цієї
таблиці?
Відповідь:
24 = 16.
9. Скількома способами можна заповнити одну
картку в лотереї "Спорт прогноз"? (В цій лотереї треба передбачити
підсумок тринадцяти. спортивних матчів. Підсумок кожного матчу – перемога
однієї з команд або нічия; рахунок не має значення.)
Відповідь:
213.
10. Алфавіт племені Мумбо-Юмбо складається з
трьох літер А, Б та В. Слово – будь-яка послідовність, яка складається не
більше як з 4 літер. Скільки слів в мові племені Мумбо-Юмбо?
Вказівка.
Підрахуйте окремо кількість одно-, дво-, три- та чотирилітерних слів.
Розв
'язок. 31+ 32 + 33 + 34 = 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. Скільки різних слів можна отримати,
переставляючи літери слова "ЛІНІЯ"?
Розв'язок.
У цьому слові дві літери І, а всі інші літери різні. Тимчасово будемо вважати різними і літери І,
позначивши їх як І1 та І2.
При цьому припущенні отримаємо 5! = 120 різних слів. Але ті слова, які
дістаються одне з одного тільки переставленням літер І1 та І2, насправді однакові, Таким
чином, отримані 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-цифрових чисел, яким не притаманна необхідна,
властивість. Оскільки це точно ті самі числа, в напису яких зустрічаються
тільки непарні цифри, то їх кількість, очевидно, дорівнює 56 = 15625.
Всього 6-цифрових чисел 900000 Тому кількість 6-цифрових чисел, яким притаманна
вказана властивість, дорівнює 900000-15625 = 884375.
Основним
моментом при розв'язуванні цієї задачі був так знаний перехід до доповнення:
підрахунок "непотрібних" варіантів замість підрахунку
"потрібних". Ось ще одна задача, розв'язуючи яку, корисно послуговуватися
цим міркуванням.
Задача
27. В абетці племені Бум-Бум шість
літер. Словом є будь-яка, послідовність, з шести літер, в якій є принаймні дві
однакові літери. Скільки слів в мові племені Бум-Бум?
Відповідь,
66 - 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. 56+4∙55 33.
36 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∙109 – 9∙9!
45. 8∙9
< 9∙106 – 8∙96, і тому чисел а одиницею більше. 46. 63-53 47. 13∙11∙9∙7∙5∙3∙1 48. 9∙107∙5
Немає коментарів:
Дописати коментар