Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

3.= (0, 1), = [ , ];

4.= , = ∩ [0, +∞);

5.= { всi iнтервали на прямiй }, = { пiвплощина пiд лiнiєю

= };

6.= , = 2;

7.= { всi послiдовностi натуральних чисел }, = { всi зростаючi послiдовностi натуральних чисел };

8.= { сфера з виколотою точкою }, = { вся площина };

9.= { всi кола з радiусом бiльшим за 4 }, = { всi кола з радiусом меншим за 4 };

10.= , = .

70

ЗАНЯТТЯ 5

Основи комбiнаторики

Навчальнi задачi

№ 5.1. Вiд мiста А до мiста В веде 3 дороги, а вiд мiста В до мiста С веде 2 дороги. Скiлькома способами можна потрапити з мiста А в мiсто С?

Розв’язок. Для кожного варiанта подорожi з мiста А в мiсто В завжди iснує 2 варiанта подорожi з мiста В в мiсто С. Так як з А в В ведуть 3 дороги, то всього з А в С можна попасти 3 · 2 = 6 способами.

A B C

№ 5.2. В клубi велосипедистiв тризначнi номери бiлетiв. Через забобоннiсть членiв клубу було вирiшено виключити з можливих цифр вiсiмку. Яка максимально можлива кiлькiсть членiв клубу?

Розв’язок. Для початку з’ясуємо, скiльки однозначних номерiв не мiстить вiсiмку. Це будуть цифри 0, 1, 2, 3, 4, 5, 6, 7, 9. Всього можливих мiсць для даних цифр три. Тому, за комбiнаторним правилом множення, кiлькiсть можливих чисел буде рiвна 9·9·9 = 729, а це i буде максимально можливою кiлькiстю членiв клубу.

71

№ 5.3. Яка мiнiмальна кiлькiсть знакiв має бути у кодi Морзе, щоб мати можливiсть передавати текст Українською мовою?

Розв’язок. За допомогою рiвно знакiв, маючи у розпорядженi 2 символа - крапку i тире, можна отримати 2 рiзних комбiнацiй тире i крапки, та закодувати за допомогою них таку ж кiлькiсть символiв. Якщо взяти тiльки один знак, то можна закодувати лише 2 символи. Якщо взяти 2 знаки, то кiлькiсть символiв, якi можливо передати, буде 2+4 = 6. Так як в Українському алфавiтi 33 символи, то потрiбно не менш нiж 33 можливих варiанти. За трьох символiв коду кiлькiсть варiантiв збiльшиться до 2+4+8 = 14, за чотирьох - до 2+4+8+16=30, а за п’я- ти - 2+4+8+16+32=62. Бачимо, що чотирьох символiв недостатньо для передачi Українського алфавiту, проте п’яти символiв вистачить навiть для тексту зi знаками пунктуацiї.

№ 5.4. Скiлькома способами з 28 фiшок домiно можна вибрати пару так, щоб їх можна було прикласти одне до одного (щоб на кожному спiвпало хоча б по однiй цифрi)?

Розв’язок. Спочатку виберемо першу фiшку домiно. Це можна зробити 28 способами. При цьому в 7 варiантах вона буде ”дублем“ - симетричною фiшкою . В рештi випадкiв, а їх буде 21, цифри на фiшцi будуть вiдрiзнятися. Для ”дублiв“ можливо вибрати лише 6 фiшок, адже на нiй лише одне число, а всього з певним числом є 7 фiшок. Тому в цьому випадку отримаємо 7 · 6 = 42 можливi варiанти. Якщо ж фiшка не є ”дублем“, то до кожної з сторiн можна прикласти по 6 фiшок. В цьому випадку отримаємо 21 · 12 = 252 варiанти. Остаточно, отримаєм

42 + 252 = 294 варiанти. Проте, в даних мiркуваннях порядок врахову-

72

вався та фiшки типу 06 та 60 вважались рiзними, тому потрiбно отриману кiлькiсть варiантiв роздiлити навпiл: 294 ÷ 2 = 147.

№ 5.5. В лiфт дев’ятиповерхового будинку сiли п’ять пасажирiв. Скiлькома способами вони можуть вийти з лiфта так, щоб всi вийшли на рiзних поверхах?

Розв’язок. Для того, щоб пасажири виходили на рiзних поверхах, потрiбно, щоб кожен наступний пасажир виходив на поверсi, на котрому не виходив нiхто iнший. Таким чином, кожен наступний пасажир "зменшує"доступну iншим кiлькiсть поверхiв для вибору. Вiдповiдно до основного принципу комбiнаторики, отримаємо 9·8·7·6·5 = 59 = 15120.

Задачi для аудиторної та домашньої роботи

№5.6. Скiльки рiзних дiльникiв має число 24?

№5.7. Скiльки є 5-значних чисел, якi дiляться на 5? Скiльки є таких

-значних чисел?

№5.8. З мiста А в мiсто В веде 10 дорiг, а з мiста В в мiсто С - 14 дорiг. Скiлькома способами можна пройти з мiста А в мiсто С i повернутися? Якщо повертатися назад iншими дорогами?

№5.9. У класi вивчають 10 дисциплiн. В п’ятницю 6 рiзних урокiв. Скiлькома способами можна скласти розклад на п’ятницю?

№5.10. 1 вересня на першому курсi одного з факультетiв заплановано за розкладом 3 лекцiї. Всього на першому курсi вивчається 10 дисциплiн. Скiльки рiзних розкладiв можна скласти?

73

№5.11. 5 хлопчикiв i 5 дiвчат сiдають на 10 розташованих поряд стiльцiв, причому хлопчики сiдають на мiсця з непарними номерами, а дiвчата - з парними. Скiлькома способами це можна зробити?

№5.12. Скiльки рiзних дiльникiв має число 24?

№5.13. Скiльки iснує 6-цифрових чисел, якi не мiстять в записi нуля i дiляться на 9?

№5.14. Кожна з вершин при основi трикутника сполучена прямими з n точками, обраними на бiчнiй сторонi, протилежнiй до цiєї вершини. На скiльки частин подiлять трикутник цi прямi? Скiльки точок перетину утвориться всерединi трикутника?

№5.15. Скiльки iснує 5-значних чисел, якi:

а) однаково читаються яз злiва на право так i справа налiво;

б) складається з непарних чисел?

№5.16. Скiльки 4-значних чисел можна утворити з цифр 0,1,2,3,4,5, якщо

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

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

№5.17. 5 польовим радiостанцiям дозволено, пiд час навчань, працювати на 6 радiохвилях. Скiльки способiв, при одночаснiй роботi всiх 5 радiостанцiй, робити так, щоб

а) хоча б 2 радiохвилi не спiвпадали; б) були використанi рiзнi радiохвилi?

№5.18. Для дидактичних матерiалiв на клаптиках картону у формi кругу, квадрату, трикутника та круга з одного боку друкують букву, а з iншого цифру. Скiльки всього рiзних об’єктiв можливо виготовити?

74

№5.19. В молекулах ДНК є 4 азотистi основи: аденiн, тимiн, гуанiн та цитозин. Всього в живих органiзмах зустрiчається 20 амiнокислот. Скiльки потрiбно взяти азотистих основ щоби зашифрувати всi необхiднi амiнокислоти?

№5.20. У Великiй Британiї прийнято давати дiтям по декiлька iмен. Скiлькома способами можна назвати дитину, якщо загальна кiлькiсть iмен 300, а дитинi дають не бiльше 3 iмен? Чи вистачить рiзних комбiнацiй iмен на все населення країни (51 млн чол)?

№5.21. Скiльки можливих комбiнацiй чисел можна записати в радянську електронно-обчислювальну машину ”Стрiла“, яка має 2048 комiрок по 43 бiта?

№5.22. У прямокутну таблицю, яка мiстить m рядкiв та n стовпцiв, записують числа 1 та -1. Скiльки рiзних таблиць можна утворити при цьому?

№5.23. Морська система семафорiв передбачає сигналiзування флажками для передачi повiдомлень. Iснує 5 положень для кожної руки. Проте, для передачi деяких букв (б, д, к, х, ю, я) обидва флажки розташованi з одного боку. Навiщо це потрiбно?

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

№5.25. На дошцi для шахiв стоять 2 тури. Скiльки способiв їх розташувати так, щоб вони не побили одна другу?

75

ЗАНЯТТЯ 6

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

Навчальнi задачi

№ 6.1. Скiлькома способами з колоди з 36 карт можна выбрати невпорядкований набiр з 5 карт так, щоб в цьому наборi було б точно два тузи, одна дама, та рiвно одна бубнова карта?

Розв’язок. Розглянемо можливi випадки.

Перший випадок - коли серед вибраних карт є бубнова дама. Її можна вибрати єдиним способом. Два тузи будуть набиратись iз трьох, адже бубнова карта уже є, а число способiв вибрати цi тузи буде 32. Залишилось вибрати ще двi карти, якi не є бубновими, та не є тузами або дамами. Таких карт буде (9 − 2) · (3 − 1) = 21, тому число варiантiв вибору цих карт буде 212 . За правилом множення, всього в цьому випадку можливо

11 · 32 · 212 = 1 · 3 · 210 = 630 варiантiв.

Другий випадок - коли серед вибраних карт є бубновий туз. Вибрати його можна єдиним способом. Залишається мiсце ще для одного туза з тих трьох, що залишись. Його можна вибрати 31 способами. Даму обираємо iз трьох не бубнових, варiантiв вибору буде 31. Залишилось набрати двi карти, якi не є бубновими, та не є тузами або дамами. Варiантiв набору таких карт знову буде 212 . За правилом множення, варiантiв набрати такий набiр буде 11 · 31 · 31 · 212 = 1 · 3 · 3 · 210 = 1890.

76

Останнiй можливий варiант - коли ми маємо карту, яка є бубновою, проте не є нi тузом, нi дамою. Обрати її можна iз семи таких карт, тобто

71 способами. Тузи вибираємо з трьох небубнових 32 способами. Дама теж вибирається з трьох небубнових 31 способом. Залишилось додати одну небубнову карту, що не є дамою або тузом. Це можна зробити 211

способом. За правилом множення, отримаємо 71· 32· 31· 211 = 7·3·3·21 = 1323 варiантiв.

Остаточно, сумуємо отриманi результати та отримуємо 630 + 1890 + 1323 = 3843 способiв вибрати заданий в умовi набiр карт.

№ 6.2. Скiльки рiзних слiв можна отримати зi слова “голова” так, щоб двi лiтери “о” не стояли поруч?

Розв’язок. Загальна кiлькiсть слiв, якi можуть бути отриманi з букв даного слова, буде дорiвнювати числу впорядкованих розбиттiв 6 - елементної множини на пiдмножини, що складаються з лiтер одного типу, тобто

(2, 1, 1, 1, 1) = (2 + 1 + 1 + 1 + 1)! = 6! = 360. 2!1!1!1!1! 2!

Якщо лiтери “о” стоять поруч, то їх можна вважати єдиним символом. Варiантiв такого результату буде (5) = 5! = 120. Остаточно, вiднявши вiд загальної кiлькостi можливих слiв кiлькiсть тих, що нам не пiдходять, отримаємо 360 − 120 = 240 слiв.

№ 6.3. У посудинi є 4 зелених, 3 бiлих та 5 чорних кульок, причому всi кульки пронумерованi. Скiлькома способами можна витягнути 7 кульок, не повертаючи їх та не враховуючи їх порядок так, щоб отримати не менш як 1 зелену, 2 бiлих та 3 чорних кульок?

77

Розв’язок. Нехай ми витягнули 1 зелених, 2 бiлих та 3 кульок. Витягнемо заданi в задачi кульки, тобто 1 зелену, 2 бiлих та 3 чорних. Всього отримали 6 кульок, тому потрiбно витягнути ще одну будь-якого кольору. Для цього потрiбно розглянути три варiанти. Якщо ми витягнули зелену кульку, то отримаємо 2 зеленi, 2 бiлi та 3 чорнi кульки. Варiантiв набрати цi кульки буде 42 · 32 · 53 = 180. Аналогiчним чином, якщо витягнути чорну кульку, отримаємо 41 · 32 · 54 = 60 варiантiв, а при витяганнi червоної кульки буде 41 · 33 · 53 = 40.

Остаточно, просумуємо всi варiанти та отримаємо 180+60+40 = 280

можливих способiв виконати потрiбнi дiї.

Задачi для аудиторної та домашньої роботи

№6.4. Скiлькома способами можна розселити 8 студентiв в трьох кiмнатах: одномiснiй, трьохмiснiй i кiмнатi на 4 мiсця?

№6.5. Сiм однакових шарикiв розсипають по чотирьом лункам (в одну лунку можна вмiстити будь-яку кiлькiсть шарикiв). Скiльки iснує рiзних способiв розподiлити сiм шарикiв по чотирьом лункам? Скiльки iснує способiв розмiщення при якому перша лунка буде порожньою?

№6.6. Кидається 10 однакових гральних костей. Розрахувати, скiльки iснує варiантiв, при яких

1.жодного разу не випаде 6 очок;

2.хоча б на однiй буде шiстка;

3.рiвно на трьох випаде 6 очок?

№6.7. Скiльки iснує 7-ми значних телефонних номерiв, в яких

78

1.4 останнi цифри однаковi;

2.всi цифри рiзнi;

3.номер починається з 5;

4.номер мiстить три цифри 5, двi 1 i двi цифри 2?

№6.8. Шiсть осiб зайшли у лiфт на першому поверсi 7-ми поверхового будинку. Скiльки буде варiантiв при яких

1.на другому, третьому та четвертому поверхах не вийде жодного пасажира;

2.троє вийдуть на сьомому поверсi;

3.на кожному поверсi вийде по однiй особi;

4.всi вийдуть на одному поверсi?

№6.9. 52 карти розподiляються мiж чотирьма гравцями (кожному по 13 карт). Скiльки варiантiв при яких

1.кожен отримає туза;

2.один гравець отримає всi 13 карт однiєї мастi;

3.всi тузи отримає один iз гравцiв;

4.два певних гравця не отримають жодного туза?

№6.10. Iз колоди з 36 карт витягають невпорядкований набiр iз 5 карт. Скiлькома способами можна витягнути набiр, у якому було б:

1.1 король, 2 дами та 1 пiкова карта;

79