§2. Прості задачі комбінаторного типу

З комбінаторними задачами читачі зазвичай стикаються задовго до того, як розпочинають систематично вивчати цей розділ математики. Такі задачі зустрічаються і в шкільних підручниках та посібниках для позакласних занять. Розглянемо деякі найпростіші задачі такого типу.

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

■ Очевидно, що за допомогою не більше як п’ятьох перевірок визначиться ключ до першого замка. Після цього не більше як чотирма випробуваннями визначиться ключ до другого замка. Потім відповідно не більше як 3 і 2 випробування дадуть змогу з’ясувати, які ключі підходять до третього і четвертого замків. Нарешті, достатньо лише одного випробування, аби підібрати ключ до п’ятого замка. Ключ, який залишиться, мусить підходити для останнього замка. Тому усього потрібно буде не більше, ніж 5 + 4 + 3 + 2 + 1  15 перевірок, аби підібрати ключі до усіх замків. А найменша можлива кількість перевірок — 5. ■

Задача 2.Скільки існує чотирицифрових чисел, які можна записати:

а)тільки непарними цифрами;

б)тільки парними цифрами;

в)цифрами різної парності?

■ а) Мова йде лише про числа вигляду 3715, 9171, 3373 та ін. Оскільки непарних цифр є 5, то першу цифру можна вибрати п’ятьма способами. Це саме можна сказати й про інші цифри. Тому шуканих чотирицифрових чисел існує 5·5·5·5625.

б) Оскільки перша цифра не може бути нулем, то її можна вибрати лише серед цифр 2, 4, 6 і 8. Кожну з інших цифр можна вибрати п’ятьма способами. Тому чотирицифрових чисел, записаних лише парними цифрами, існує 4·5·5·5  500.

в) Усіх чотирицифрових чисел є 9·10·10·109000. Якщо ми відкинемо ті з них, які записуються тільки непарними або тільки парними цифрами, то дістанемо чотирицифрові числа, у записі яких містяться і парні, і непарні цифри. Отже, таких чисел існує 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 – 1617.

Очевидно, що натуральних чисел, які не перевищують 99 і діляться на 2 або на 3, є 49 + 33 – 16 66. Відповіддю на запитання є) буде: 99 – 6633.■

Зрозуміло, що можна розглядати й інші аналогічні запитання. Наприк-лад: скільки існує натуральних чисел, які не перевищують 1000 і не діляться ні на 5, ні на 6, ані на 7. Поясніть, чому відповіддю на таке запитання є:

Задача 4.Скільки існує двоцифрових чисел, менших від 100, цифри яких:

а)розміщені в порядку зростання (тобто перша цифра менша від другої);

б)у порядку спадання;

в)у не зростаючому порядку (перша цифра більша або дорівнює другій)?

■ а) У першому десятку таких чисел немає, у другому їх 8, бо числа 10 та 11 потрібної властивості не мають. І так далі. Усіх двоцифрових натуральних чисел, які не перевищують 100 і в записі яких цифри розміщені в порядку зростання, є 8 + 7 + 6 + 5 + 4 + 3 + 2 + 136.

б) У порядку спадання цифри розміщені у числах 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).