- •Мирон Маланюк, Василь Кравчук Метод математичної індукції та елементи комбінаторики
- •Передмова редактора
- •§1. Метод математичної індукції
- •§2. Прості задачі комбінаторного типу
- •§3. Загальні правила комбінаторики
- •§4. Основні поняття комбінаторики
- •4.1. Перестановки
- •4.2. Розміщення
- •4.3. Комбінації
- •4.4. Деякі комбінаторні тотожності
- •§5. Сполуки з повторенням елементів
- •5.1. Перестановки з повтореннями
- •5.2. Комбінації з повтореннями
- •5.3. Розміщення з повтореннями
- •§6. Приклади розв’язування комбінаторних задач
- •§7. Формула бінома Ньютона
- •Заключне зауваження
- •Задачі для самостійного розв’язування Завдання і
- •Обов’язкові задачі
- •Додаткові задачі
- •Завдання 2 Обов’язкові задачі
- •Додаткові задачі
- •Задачі для підготовки до математичних олімпіад
- •Відповіді та вказівки до задач математичних олімпіад
- •Список рекомендованої літератури
- •§1. Метод математичної індукції 8
§2. Прості задачі комбінаторного типу
З комбінаторними задачами читачі зазвичай стикаються задовго до того, як розпочинають систематично вивчати цей розділ математики. Такі задачі зустрічаються і в шкільних підручниках та посібниках для позакласних занять. Розглянемо деякі найпростіші задачі такого типу.
Задача 1.Є 6 замків і 6 ключів до них. Кожний ключ підходить лише до одного замка. Вставляючи ключ у замок, можна з’ясувати, підходить він до цього замка чи ні. Скільки таких перевірок потрібно провести, аби підібрати ключі до усіх замків?
■ Очевидно, що за допомогою не більше як п’ятьох перевірок визначиться ключ до першого замка. Після цього не більше як чотирма випробуваннями визначиться ключ до другого замка. Потім відповідно не більше як 3 і 2 випробування дадуть змогу з’ясувати, які ключі підходять до третього і четвертого замків. Нарешті, достатньо лише одного випробування, аби підібрати ключ до п’ятого замка. Ключ, який залишиться, мусить підходити для останнього замка. Тому усього потрібно буде не більше, ніж 5 + 4 + 3 + 2 + 1 15 перевірок, аби підібрати ключі до усіх замків. А найменша можлива кількість перевірок — 5. ■
Задача 2.Скільки існує чотирицифрових чисел, які можна записати:
а)тільки непарними цифрами;
б)тільки парними цифрами;
в)цифрами різної парності?
■ а) Мова йде лише про числа вигляду 3715, 9171, 3373 та ін. Оскільки непарних цифр є 5, то першу цифру можна вибрати п’ятьма способами. Це саме можна сказати й про інші цифри. Тому шуканих чотирицифрових чисел існує 5·5·5·5625.
б) Оскільки перша цифра не може бути нулем, то її можна вибрати лише серед цифр 2, 4, 6 і 8. Кожну з інших цифр можна вибрати п’ятьма способами. Тому чотирицифрових чисел, записаних лише парними цифрами, існує 4·5·5·5 500.
в) Усіх чотирицифрових чисел є 9·10·10·109000. Якщо ми відкинемо ті з них, які записуються тільки непарними або тільки парними цифрами, то дістанемо чотирицифрові числа, у записі яких містяться і парні, і непарні цифри. Отже, таких чисел існує 9000 – (625 + 500)7875.■
Задача 3.Скільки існує натуральних чисел, менших від 100, які:
а)діляться на 2;
б)не діляться на 2;
в)діляться на 3;
г)діляться одночасно і на 2, і на 3;
ґ)діляться на 2, але не діляться на 3;
д)діляться на 3, але не діляться на 2;
е)діляться або на 2, або на 3;
є)не діляться ні на 2, ні на 3?
■ При відшуканні відповідей на ці запитання можна було б виписати всі натуральні числа від 1 до 99 і полічити, скільки серед них таких, які нас цікавлять. А можна відшукати закономірності, яким підпорядковані числа кожного з указаних видів. Наприклад, на 2 діляться лише парні натуральні числа 2, 4, 6, ..., 98. Їх, очевидно, — 49. Це число можна дістати як цілу частину від дробу(адже натуральних чисел, менших від 100, є 99, а на 2 ділиться кожне друге натуральне число). Цілу частину числа позначають за допомогою квадратних дужок, наприклад:.
Відповідь на запитання б) з’ясовується просто. Чисел, які не діляться на 2, є 99 – 49 50.
На 3 ділиться кожне третє число із послідовності перших 99 натуральних чисел, а саме: 3, 6, 9,..., 96, 99. Їх існує .
Аби відповісти на запитання г), можна було б відшукати, скільки натуральних чисел, менших від 100, ділиться на 6. Їх існує . Відповідь можна знайти й так: з послідовності чисел 3, 6, 9, 12, ..., 96, 99, кратних 3, вибрати лише парні числа; їх єВідповідь на це запитання дістали б, якби обчислилиПодумайте і поясніть чому.
Натуральних чисел, які менші від 100, діляться на 2, але не діляться на 3, є 49 – 16 33. Чисел, які діляться на 3, але не діляться на 2, є 33 – 1617.
Очевидно, що натуральних чисел, які не перевищують 99 і діляться на 2 або на 3, є 49 + 33 – 16 66. Відповіддю на запитання є) буде: 99 – 6633.■
Зрозуміло, що можна розглядати й інші аналогічні запитання. Наприк-лад: скільки існує натуральних чисел, які не перевищують 1000 і не діляться ні на 5, ні на 6, ані на 7. Поясніть, чому відповіддю на таке запитання є:
Задача 4.Скільки існує двоцифрових чисел, менших від 100, цифри яких:
а)розміщені в порядку зростання (тобто перша цифра менша від другої);
б)у порядку спадання;
в)у не зростаючому порядку (перша цифра більша або дорівнює другій)?
■ а) У першому десятку таких чисел немає, у другому їх 8, бо числа 10 та 11 потрібної властивості не мають. І так далі. Усіх двоцифрових натуральних чисел, які не перевищують 100 і в записі яких цифри розміщені в порядку зростання, є 8 + 7 + 6 + 5 + 4 + 3 + 2 + 136.
б) У порядку спадання цифри розміщені у числах 10, 20, 21, 30, 31, 32 і т. д. Якщо міркувати так само, як і в першому випадку, то знайдемо 45 двоцифрових чисел, цифри яких розміщені у порядку спадання.
в) Є 9 двоцифрових чисел 11, 22, 33, 44, 55, 66, 77, 88, 99, цифри яких рівні між собою. Про ці числа можна сказати, що їхні цифри розміщені у не зростаючому (або, якщо потрібно, — у не спадному) порядку. Тому чисел, цифри яких розміщені у не зростаючому порядку, існує 45 + 9 54. ■
Задача 5.Є чотири кульки однакових розмірів, але різної маси. За допомогою скількох зважувань на шалькових терезах без важків можна розмістити ці кульки в порядку спадання їхніх мас?
■ Очевидно, що кожне зважування двох кульок дає змогу визначити, яка з них має більшу, а яка меншу масу.
Два зважування дають змогу виділити у двох парах важчі і легші кульки. Третє зважування визначає серед двох важчих кульок найважчу, а четверте серед двох легших — найлегшу. Знаючи серед чотирьох кульок найважчу і найлегшу, за допомогою п’ятого зважування упорядкуємо маси двох кульок, що залишилися. ■
Задача 6.Шість студентів, присутніх у кімнаті, знають англійську мову, стільки ж — німецьку, і сім студентів знають французьку мову. Один із цих студентів знає всі три згадані мови, чотири студенти знають німецьку та англійську, два — французьку та англійську, а три — німецьку та французьку мови. Скільки усіх присутніх у кімнаті, якщо кожен з них знає хоча б одну зі згаданих мов?
■ При розв’язуванні цієї задачі доцільно скористатися табличним записом.
Якби з кімнати вийшов той студент, який знає усі три мови, то дістали б ситуацію, яка описується другим рядком таблиці. Якби вийшли ті студенти, які знають по дві іноземні мови, ситуація відображалася б третім рядком. Тоді в кімнаті залишилося б лише 4 студенти. Оскільки вийшло 7 студентів, то шукана відповідь — 11. ■
-
а
н
ф
ан
аф
нф
анф
Спочатку
6
6
7
4
2
3
1
Після першого виходу
5
5
6
3
1
2
0
Після другого виходу
1
0
3
0
0
0
0
Задача 7.(Жартівлива задача Льюїса Керролла.) У жорстокому бою 70 зі 100 піратів втратили по оку, 75 втратили вухо, 80 були поранені в руку і 85 — в ногу. Яка мінімальна кількість тих, хто зазнав одночасно всіх чотирьох поранень, тобто був поранений в око, вухо, руку і в ногу?
■ Якби усі 30 піратів, що зберегли свої очі, були поранені у вухо, то 45 були б поранені двічі (в око і у вухо). Отже, було б лише 55 піратів з одним пораненням в око або у вухо. Коли б усі ці 55 піратів були поранені в руку, то було б лише 25 піратів, які дістали три поранення (в око, вухо і в руку), і 75 мали б лише два поранення. Коли б усі ці 75 піратів були поранені в ногу, то ще 10 чоловік мали б четверте поранення. Це і є мінімальна кількість людей, які могли б дістати усі чотири поранення. Зрозуміло, що максимальною кількістю потерпілих, які могли б дістати усі 4 поранення, є 70.■
Аналогічні задачі, які підводять до усвідомлення комбінаторних закономірностей, можна зустріти у багатьох посібниках, зокрема у книзі М. П. Маланюка та В. І. Лукавецького «Олімпіади юних математиків», виданій у Києві видавництвом «Радянська школа» в І977 році (ст. 37–40).