Комбінаторика
У багатьох олімпіадних задачах потрібно визначити кількість способів, якими можна здійснити вибір при заданих умовах. У цьому нам допоможе розділ математики під назвою комбінаторика. Його вивчення почнемо із двох основних правил.
Правило суми: якщо деякий об’єкт А можна вибрати m способами, а інший об’єкт В можна вибрати n способами, то вибір «або А, або В» можна здійснити m+n способами.
Приклад 1. Із Мадриду до Барселони ходять 3 потяги. Після збільшення кількості туристів влада Іспанії пустила 5 додаткових автобусних рейсів. Скількома способами можна дістатися із Мадриду до Барселони?
Розв’язання. Можна сісти на один із трьох потягів – 3 варіанти, або на один із п’яти автобусів – що додаткові 5 варіантів. Разом маємо 5+3=8 варіантів.
Правило добутку: якщо деякий об’єкт А можна вибрати m способами і після кожного такого вибору інший об’єкт В можна вибрати n способами, то вибір пари А і В можна здійснити m·n способами.
Приклад 2. Із Риму до Флоренції літають 3 авіарейси. Із Флоренції до Венеції літають 5 авіарейсів. Скількома способами можна дістатись із Риму до Венеції?
Розв’язання. Після прильоту з Риму до Флоренції першим рейсом, маємо 5 варіантів продовження подорожі (можемо сісти на будь-який із 5 літаків до Венеції). Після прильоту з Риму до Флоренції другим рейсом, маємо знову ще 5 варіантів продовження подорожі. І так само маємо 5 варіантів після прильоту з Риму до Флоренції третім рейсом. Тому усього маємо 5·3=15 варіантів.
Приклад 3. У 5 класі 12 учнів. Скількома способами можна вибрати старосту та його заступника?
Розв’язання. Старостою може бути будь-хто із 12 учнів. Маємо 12 способів. Після вибору старости, заступника можемо вибрати 11 способами (після вибору старости залишилось 11 кандидатів на посаду заступника). Тому всього є 12·11=132 способи.
Задачі для самостійного розв’язання.
1. У магазині «Світ чаю» подається 5 сортів чаю та 9 видів тортиків. Скількома способами можна замовити собі десерт із чашечки чаю та шматочка тортика?
2. У футбольній команді потрібно вибрати нападаючого та воротаря. Скількома способами можна це зробити? (У футбольній команді 11 гравців).
3. У 5 класі 12 учнів. Скількома способами можна вибрати двох чергових?
4. Абетка племені Мумбо-Юмбо Складається із трьох літер: @, #, &. Словом називається будь-яка послідовність, що складається не більше ніж із 4 літер. Скільки всього слів у мові племені Мумбо-Юмбо?
5. Кожну клітинку квадратної таблиці 2×2 можна пофарбувати у білий або у чорний колір. Скільки існує різних розфарбовок цієї таблиці?
6. Меню шкільної їдальні складається із 6 страв. Ненажерливий внучок, який з’їв усі бабусині млинці, прийшов до школи. Для різноманіття він хоче кожного дня замовляти такий набір страв, якого іще не замовляв (при цьому кількість страв неважлива – він може замовити усі 6 страв одночасно, а може замовити тільки 1 страву або і зовсім жодної). Скільки днів онучок зможе так харчуватись?
7. Скільки існує різних семизначних телефонних номерів (вважаємо, що номер не може починатися з 0)?