Математичний дивертисмент «Логічні задачі»

Математичний дивертисмент  «Логічні задачі»

1. Батько із сином потрапили в автомобільну катастрофу. Батько по­мер у шпиталі. До сина в палату заходить хірург і говорить, вказуючи на нього: «Цс мій син». Чи можуть ці слова бути правдою?

2. Скільки цифр "9" у ряді чисел від 1 до 100?

3. Самотній нічнийсторож помер вдень. Чи отримує він пенсію?

4 .Цеглина важить  один кілограм плюс ще півцеглини. Скільки важить цеглина?

5. Під яким кущем сидить заєць під час дощу?

6. Якщо ви любите граматику, то вас зацікавить питання, як правиль­но сказати "не бачу былий жовток» чи «не бачу білого жовтка"?

7. Дах одного будинку не є симетричним. Один його нахил складає з горизонталлю кут 60 градусыв, а інший кут 70 градусів. Припустимо, що півень кладе яйце на гребынь даху. На який бік даху впаде яйце? .

8.. Припустимо, що  на кордоні США та Канади сталася авіаційна ката­строфа. У якый з двох країн повинні бути поховані уцілілі пасажири?

9. За кордон поїхала група туристів із 100 чоловік. 10 із них не знали ні німецької, ні  французької мови. 75 знали німецьку мову. 83 людини знали французьку мову. Скільки туристів володіли двома іноземними мовами?

10. У сім’ї троє дітей. Тоні вдвоє більше років, ніж буде Галі тоді, коли Жені виповниться стільки ж років, скільки Тоні зараз. Хто з них найстар­ший, хто найменший, а  хтосередній за віком?

11. На одному заводі працювало троє друзів: слюсар, токар і зварю-вальник. Їхні прізвища: Ярема, Заполух і Стецюк. У слюсаря немає ні бра­тів, ні сестер. Він — иймолодший з друзів. Стецюк, що одружений на сестрі Яреми, старший від токаря. Назвіть прізвища слюсаря, токаря і зварюваль-ника.

12. Морозенко, Соняк і Покиданець живуть на одній вулиці. Один із них - столяр, ;Ірутий - маляр, а третій - бухгалтер.

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

Відомо також, що Покиданець ніколи не чув про Соняка. Хто чим за­
ймається?

Відповіді

1. Так, хірург — мати сина.
2. .20.
3. Ні, бо він помер.
4. 2кг.
5. Під мокрим.
6. Жовток не буває білим.
7. Півень не кладе яєць.
8. Пасажирів, які уціліли, не потрібно ховати.
9. 68 чоловік.
10. Найстарша - Тоня, а Галя - наймолодша.
11. Слюсар Заполух, токар Ярема і зварювальний Стецюк.
12. Покиданець - бухгалтер, Морозенко - столяр, Соняк - маляр.

              

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

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то AÈB містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то пари A∙B містить m∙n елементів, тобто пар.

Кількість елементів множини A будемо далі позначати |A|.

Ці правила мають також інше формулювання:

Принцип суми. Якщо об'єкт A можна вибрати m способами, а об'єкт B – n іншими способами, то вибір "або A, або B" можна здійснити m+n способами.

Принцип добутку. Якщо об'єкт A можна вибрати m способами і після кожного такого вибору об'єкт B може бути вибраним n способами, то вибір "A і B" в указаному порядку можна здійснити m×n способами.

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

Правило добутку застосовується для підрахунку кількості об'єктів, що розглядаються як елементи декартових добутків відповідних множин. Отже, ці об'єкти являють собою скінченні послідовності – пари, трійки тощо.

Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

Означення. Розміщення з повтореннями по m елементів n-елементної множини A – це послідовність елементів множини A, що має довжину m.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Якщо |A|=n, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина Am=A´A´…´A, містить nm елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2m. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини m.

У багатьох комбінаторних задачах об'єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A1, другий – A2, тощо. Але досить часто множина A2 визначається лише після того, як зафіксовано перший член послідовності, A3 – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A1|=10, |A2|=|A3|=…=|A7|=9, і загальна кількість номерів є 10×96.

2. Розміщення та перестановки без повторень

Означення. Розміщення по m елементів n-елементної множини A, де m£n – це послідовність елементів множини A, що має довжину m і попарно різні члени.

Приклади.

1. При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c), (b,a), (b,c), (c,a), (c,b).

2. Розподіл n різних кульок по одній на кожний з m різних ящиків, m£n. Ящики можна пронумерувати від 1 до m, кульки – від 1 до n. Тоді кожному розподілу взаємно однозначно відповідає послідовність довжини m попарно різних номерів від 1 до n.

Неважко підрахувати кількість послідовностей з прикладу 2. На першому місці може стояти будь-який із номерів 1, …, n. На другому – незалежно від того, який саме був на першому, будь-який із n-1, що залишилися. І так далі. За принципом добутку, таких послідовностей

n×(n-1)×…×(n-m+1),

або n!/(n-m)!.

Цей добуток позначається Аⁿ_m.

Означення. Перестановка n елементів множини A без повторень – це розміщення по n елементів, тобто послідовність елементів множини A, що має довжину n і попарно різні члени.

Приклад. При A={a, b, c} усі перестановки –це трійки (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Очевидно, що кількість перестановок n елементів дорівнює кількості розміщень по m при m=n, тобто n!. Отже, 1·2·..·n=n!.

3. Комбінації без повторень

Означення. Комбінація по m елементів n-елементної множини – це її m-елементна підмножина.

Приклади.

1. При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b}, {a,c}, {b,c}.

2. Розподіл n різних кульок по одній на кожний з m однакових ящиків, m£n. Оскільки ящики однакові, то розподіл взаємно однозначно визначається підмножиною з m кульок, що розкладаються.

З кожної m-елементної комбінації елементів n-елементної множини можна утворити m! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є  

С ⁿ_m = ^n! /_{( m!(n-m)!)}

 Ця кількість позначається:  С ⁿ_m.

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

Означення. Перестановка з повтореннями по m елементів множини A={a1, a2, …, an} складу (k1, k2, …, kn) – це послідовність довжини m=k1+k2+…+kn, в якій елементи a1, a2, …, an повторюються відповідно k1, k2, …, kn разів.

Приклади.

1. При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

ФОРМУЛИ КІЛЬКОСТІ ЕЛЕМЕНТІВ СКІНЧЕНИХ МНОЖИН

ФОРМУЛИ   КІЛЬКОСТІ   ЕЛЕМЕНТІВ  СКІНЧЕНИХ  МНОЖИН

Дуже важливими для практичних  задач є формули  підрахунку кількості різних елементів у декількох множинах, що містять спільні елементи, тобто кількості елементів в об’єднанні двох або трьох множин.

Кількість елементів об'єднання  п(А+В)  будь-яких двох скін­ченних множин А і В обчислюється за формулою:

п(А+В) = п(А) + п(В) - п(АВ).

Для будь-якої трійки скінченних множин А₁, А₂, А₃ має місце формула кількості елементів множини п(A₁ +А₂ +А₃) , що є об’єднанням трьох множин, тобто 

A₁+ А₂ +А₃:

п(A₁ +А₂ +А₃) = п(А₁) + п(А₂) + п(А₃) - п(А₁А₂) - п(А₁ А₃) - п(А₂А₃) + п(А₁А₂ А₃).

Наводимо приклад використання поданих вище формул.

Задача . У лабораторії науково-дослідного інституту працює декілька чоловік, причому кожний з них знає хоча б одну іноземну мову, 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 чоловіка.

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то об’єднання двох множин A+B містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то добуток двох множин AB містить m∙n елементів, тобто пар.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c). Або, принцип добутку: 3∙3=9 пар.

Приклад. В одному з відділів магазину покупці зазвичай купляють або один торт, або коробку цу­керок. Одного дня було продано 57 тортів та 36 коробок цукерок. Скільки було покупців, якщо 12 з них придбали і торт, і коробку цукерок? Використаємо принцип суми: 57 + 36 - 12 = 81.

Задачі на круги Ейлера

Задача 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 не вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?

Задачі комбінаторики

Варіант 1

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

2.    В алфавіті деякого коду є сім ієрогліфів  і вісім цифр. Скількома способами можна закодувати інформацію за допомогою коду, що складається із двох символів алфавіту, серед яких обов’язкова тільки одна цифра і тільки одна буква. 

3.    У шкільній бібліотеці маємо десять різних книг Тараса Шевченка,  три різні книги Григорія Сковороди, тринадцять різних книг Миколи Гоголя. Скількома способами учень може зробити вибір трьох книг так, що серед них була одна книга будь-якого автора?

4.    Маємо 5 різних стільців і 7 рулонів різного кольору для оббивки стільців. Скількома  способами можна здійснити оббивку стільців?

5.    Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 4, ні на 5, ні на 7?

6.    Для автомобільних номерів використовуються 10 цифр і 28 вісім букв. Кожний номер складається з із трьох букв і чотирьох цифр(окрім номера 00-00). Яке найбільше число машин може отримати номер?

7.    Алфавіт має 33 букви. Скільки можна скласти слів, що містять не більше чотирьох букв, якщо у словах усі букви різні?

8.    В організації ООН визнано п’ять міжнародних мов спілкування. Скільки треба мати двомовних словників в цій організації для перекладу, щоб   перекладати із будь-якої міжнародної мови на будь-яку іншу міжнародну мову.

9.    Скількома способами із 30 учнів класу можна утворити актив класу, в наступному складі: лідер, замісник лідера, староста, редактор класної стінгазети?

10.    У класі 10 юнаків і 12 дівчат. Для участі в концерті потрібно виділити танцювальний дует (юнак + дівчина), тріо гітаристів(троє дівчат). Скількома способами можна це здійснити?

11.    Скільки  існує п’ятицифрових  натуральних чисел, для яких виконується умова чергування парності цифр у десятковому записі?

12.    У футбольному чемпіонаті беруть участь 16 команд.  Скільки ігор мають зіграти усі команди, якщо кожна команда грає дві гри, у себе дома і на виїзді? Чи може цей чемпіонат пройти у весняний та осінній періоди, якщо на один день весни або осені припадає тільки одна гра чемпіонату?

13.    Скільки цифр "9" у ряді чисел від 1 до 100?

14.    За кордон поїхала група туристів із 100 чоловік. 10 із них не знали ні німецької, ні  французької мови. 75 знали німецьку мову. 83 людини знали французьку мову. Скільки туристів володіли двома іноземними мовами?

15.    На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються: а) різними шляхами; б) однаковими шляхами.

16.    Скільки різних цілих дільників має число 2²∙4³?

17. Із загону у 50 скаутів,  серед яких є наймолодший скаут Макс визначається караул із 4 чоловік. Скільки різних способів утворити караул?  Допоможіть Максу знайти у скількох випадках він попадає в караул.

18. В класі вивчають 10 предметів. В понеділок 6 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок, якщо дві математики(алг. та геом.) стоять підряд?

19. 4 хлопчиків і 4 дівчаток сідають в ряд на 8 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити?

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

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

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

Задачі комбінаторики

   Варіант  2

1. В магазині "Все до чаю"  є п'ять різних чашок та 3 різних блюдця. Скількома способами можна купити чашку з блюдцем?

2. В магазині "Все до чаю" є п'ять різних чашок та 3 різних блюдця та  4 чайні ложки. Скількома способами можна купити комплект з чашки, блюдця та ложки?

3. В Країні Чудес є три міста: А, Б і В. З міста А в місто Б ведуть 6 доріг, а з міста Б у місто В – 4 дороги . Скількома способами можна проїхати від А до В?

4. Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 2, ні на 3, ні на 5?

6. Назвемо натуральне число "симпатичним", якщо в його запису зустрічаються тільки непарні цифри. Скільки існує 5-цифрових "симпатичних" чисел?

7.  Монету кидають тричі. Скільки різних послідовностей орлів та решок можна при цьому отримати?

8. Кожну клітинку квадратної таблиці 3x3 можна пофарбу­вати в чорний або білий колір. Скільки існує різних розфарбувань цієї таблиці?

9. Скількома способами можна заповнити одну картку в ло­тереї "Спорт прогноз"? (В цій лотереї треба передбачити підсумок тринадцяти  спортивних матчів. Підсумок кожного матчу – перемога однієї з команд або нічия; рахунок не має значення.)

10. Алфавіт племені Мумбо-Юмбо складається з трьох літер А, Б та В. Слово – будь-яка послідовність, яка складається не більше як з 4 літер. Скільки слів в мові племені Мумбо-Юмбо?

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

12. У футбольному чемпіонаті беруть участь 14 команд.  Скільки ігор мають зіграти усі команди, якщо кожна команда грає дві гри, у себе дома і на виїзді? Чи може цей чемпіонат пройти у весняний та осінній періоди, якщо на один день весни або осені припадає тільки одна гра чемпіонату?

14.  За кордон поїхала група туристів із 120  чоловік. 21 із них не знали ні німецької, ні  французької мови. 85 знали німецьку мову. 93 людини знали французьку мову. Скільки туристів володіли двома іноземними мовами?

15. Є група школярів, серед яких п'ють тільки каву 12, п'ють тільки чай – 10, п'ють тільки йогурт – 8, п'ють тільки каву і чай – 5, п'ють тільки каву і йогурт – 4, п'ють тільки чай і йогурт – 3, усі три напої – 1. Скільки всього школярів у групі?

16. Скільки існує непарних  п’ятицифрових чисел, для запису яких використовуються тільки цифри: а) 6, 2, 3, 4, 7;  б) 0, 4, 1, 6, 5?

17. На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються: а) різними шляхами; б) однаковими шляхами.

18. Скільки різних цілих дільників має число 3³∙5²?

19. Із загону у 30 скаутів,  серед яких є наймолодший скаут Джон визначається караул із 3 чоловік. Скільки різних способів утворити караул?  Допоможіть Джону знайти,  у скількох випадках він попадає в караул.

20. В класі вивчають 14 предметів. В понеділок 7 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок?

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

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

21. Скільки різних слів можна утворити переставлянням букв у слові «футуристика»?

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

23. У спортивному таборі  65  дітей вміють грати в футбол, 70  — у волейбол і  75  — у баскетбол. Всього дітей у таборі 100.  Яка а)найменша ; найбільша кількість дітей, які вміють грати і у футбол, і у баскетбол, і у волейбол?

Задачі комбінаторики

Варіант 3

1.В їдальні маємо  3 перших страви, і 2 других страв. Скількома способами можна скласти  обід із двох страв?

2. В алфавіті деякого коду є 4 ієрогліфи  і сім цифр. Скількома способами можна закодувати інформацію за допомогою коду, що складається із двох символів алфавіту, серед яких обов’язкова тільки одна цифра і тільки одна буква. 

3.У шкільній бібліотеці маємо сім різних книг Тараса Шевченка,  дві різні книги Григорія Сковороди, вісім  різних книг Миколи Гоголя. Скількома способами учень може зробити вибір трьох книг так, що серед них була одна книга будь-якого автора?

4. Маємо 5 різних стільців і 7 рулонів різного кольору для оббивки стільців. Скількома  способами можна здійснити оббивку стільців?

5.  Скільки цифр "2" у ряді чисел від 1 до 100?

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

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

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

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

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

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

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

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

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

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

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

15.У розиграші першості країни з футбола бере участь 16 команд. Скількома способами можуть бути розподілені золота і срібна медалі?

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

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

18. Скільки діагоналей у правильному а)шестикутнику; б) семикутнику?

19. 3 хлопчиків і 3 дівчаток сідають в ряд на 6 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити?

20. Скільки різних слів можна утворити переставкою букв у слові «арифметика»?

21. Скільки різних дільників має число 8²∙9⁴?

22. Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 30 букви  алфавіту.

23. На танцмайданчику зібралися 8 юнаків та 8 дівчат. Скількома способами вони можуть розбитися на пари для участі в черговому танці?     

24. Чемпіонат України по шахам проводиться в одне коло. Скільки грається партій, якщо участь беруть 18 шахматистів?

25. Скількома способами можна поселити 7 студентів у 3 кімнати: одномісну, двомісну та чотиримісну?     

26. Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 2, ні на 3, ні на 5?

27. У класі з 40 учнів 30 уміють плавати, 27 уміють грати у шахи і тільки 5 не вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?

28. У групі зі 100 туристів 70 знають ан­глійську мову, 45 - французьку і 23 - знають обидві мови. Скільки туристів у групі не знають ні англійської, ні французької?

ЗРАЗКИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ КОМБІНАТОРИКИ

ЗРАЗКИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ  КОМБІНАТОРИКИ ДЛЯ УЧНІВ 8 КЛАСУ

Задача 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₁∙ 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 трикутників.

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

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

Розв'язання. Перенумеруємо усі стільці і усі кольори. Перший стілець можна обтягнути 6 способами. Залишилося 5 різних кольорів вільних.  Другий стілець можна обтягнути 5 способами. Залишилося 4 різних кольорів вільних. Третій стілець можна обтягнути 4 способами. Залишилося 3 різних кольорів вільних. Четвертий стілець можна обтягнути 3 способами. Залишилося 2 різних кольорів вільних.  П’ятий стілець можна обтягнути 2 способами. Залишилося 1 колір вільний. Шостий стілець можна обтягнути 1 способом. Залишилося 0 кольорів і більше немає стільців.

За правилом добутку отримаємо Р₆ = 1∙2∙3∙4∙5∙6=6! = 720.

Відповідь: n = 720.

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

Відповідь: n = Р₁₀=1∙2∙3∙4∙5∙6∙7∙8∙9∙10 = 10!

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

Розв'язання.

Перестановкою без повторень (за умовою) заданих цифр можна утворити чотиризначне або тризначне (з нулем на першому місці) числа. Ніяк інакше такі числа отримати не можна. Загальна кількість перестановок чотирьох елементів без повторень Р =4∙3∙2∙1. З них перестановок з нулем на першому місці. Звідси шукана кількість чотиризначних чисел дорівнює n= 3∙3∙2∙1=18.

Відповідь: n = 18.

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

Розв'язання.

Кількість триколірних смугастих прапорів, що скла­дені з тканини 5 кольорів, дорівнює числу розміщень без повторень 5 кольорів по трьох місцях на прапорі:

                                                       5∙4∙3 = 60

Якщо ж одна із смуг червона, то її на прапорі можна розташувати трьома способами. Для кожного з таких роз­міщень червоної смуги два кольори для смуг, що залиши­шся, можна вибрати з чотирьох кольорів і розмістити по двох місцях на прапорі  4∙3 = 12 способами. За правилом добутку з червоною смугою можна скласти

1∙4∙3 + 1∙4∙3 + 1∙4 ∙3 = 3∙4∙3 = 36 прапорів.

Відповідь: n₁ = 60,  n₂ = 36.

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

Розв'язання.

Йдеться про вибір трійки токарів з восьми з подальшим розміщенням їх біля трьох верстатів, що виготовляють різні деталі. Тому  n = 8∙7∙6 = 336.

Відповідь: n = 336.

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

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

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

Відповідь:  n = 11∙10∙9∙8∙7.

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

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

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

Розв'язання.

Загальна кількість можливих списків промовців дорівнює Р₅ = 5! = 120. З  них у половині списків Б виступає за А. Тому: 1) n₁=60.

Якщо ж Б повинен виступити відразу за А, то, вважаючи пару (А, Б) співпромовцями однієї доповіді, дістанемо, що 2) n₂ = 4! = 24 – кількість списків доповідей.

Відповідь: n₁ = 60,  n₂ = 24.

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

Розв'язання.

З п'яти цифр можна утворити: одноцифрові, двоцифрові, ..., п'ятицифрові числа. Одноцифрових натуральних чисел, очевидно, буде чотири. Процес утворення двоцифрового числа можна описати так: з п'яти цифр на місце десятків можна 4 цифри(бо нуль не можна поставити на перше місце), а на місце одиниць можна поставити чотири цифри(бо одну цифру вже використали), таким чином, на двоцифрових чисел  4∙4 = 16.

Вибравши три цифри з п'яти і розмістивши їх на міс­цях для числа сотень, десятків і одиниць,  отримаємо

n₃  = 4∙4∙3 = 48 чисел

Аналогічно,

n₄ = 4∙4∙3∙2 = 96;

n₅ = 4∙4∙3∙2∙1 = 96.

Загальна ж кількість чисел

K =   n₁+ n₂+ n₃+ n₄+ n₅= 4 + 16 + 48+96 + 96 =260.

Відповідь: 260.

10. У Ніни є сім різних книг з математики, а у Мирослави – дев’ять різних книг з української літератури. Скількома способами вони можуть обмінятися один з одним п’ятьма книгами?

Розв’язання. Так як 5 різних книг із 7 можливих книг  можна вибрати: (7∙6)/(1∙2)=21, отже 21 спосіб може запропонувати Ніна. Так як 5 різних книг із 9 можливих книг  можна вибрати: (9∙8∙7∙6∙5)/(1∙2∙3∙4∙5)=126, отже 126 способів може запропонувати Мирослава. Таким чином число всіляких обмінів, згідно правилу добутку рівно 21∙126 =2646 способів.

Відповідь. 2646.

11. Номер автобусного квитка складається з 6 цифр. Квиток називають щасливим, якщо сума перших трьох цифр його номера рівна сумі трьох останніх цифр. Які автобусні квитків більше: щасливих чи тих, чиї номери діляться на 11?

Розв’язання. Щасливі квитки, згадані в умові, називатимемо щасливими по-київські. Назвемо квиток щасливим по-вінницьки, якщо сума цифр його номера, що стоять на парних місцях, рівна сумі цифр, що стоять на непарних місцях.

З'ясуємо спочатку, які щасливі квитків більше  по-київські або по-вінницькі? Їх порівну, оскільки між ними можна встановити взаємно однозначну відповідність таким чином. Переставимо цифри номера квитка, щасливого по-київськи: перші три цифри поставимо на непарні місця (перше, третє і п'яте), а останні три цифри  на парних (наприклад, номер 129345 перетвориться на 132495.) Отримаємо щасливий по-вінницьки квиток.

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

Довідка. Ознака подільності на 11: «Число ділиться на 11,  тоді і тільки тоді, коли сума його цифр, що стоять на парних місцях, мінус сума цифр,  що стоять на непарних місцях, ділиться на 11».

Відповідь.  Квитків з номерами,  що діляться на 11 більше.

Задачі для самостійного опрацювання

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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