Комбінаторні задачі математичних олімпіад

ustify">     Цю  перестановку також будемо називати комбінацією по m елементів множини {, , …, } з повтореннями складу (, , …, ).

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

8. Формули включень і виключень.

     Кількість елементів об'єднання двох множин, що не перетинаються, є сумою їх кількостей. Але якщо множини перетинаються, то елементи перетину при цьому додаванні  кількостей враховуються двічі. Тому їх кількість треба один раз відняти: |AB|=|A|+|B|-|A∩B|. (*)

     При обчисленні |ABC| додавання |A|+|B|+|C| веде до того, що елементи кожного з перетинів |A∩B|+|B∩C|+|A∩C| враховуються двічі, тому їх треба по одному разу відняти. Якщо перетин A∩B∩C порожній, то в результаті кожний елемент об'єднання враховано по одному разу, і все гаразд. Якщо ні, то в результаті елементи цього перетину тричі додаються і тричі віднімаються, тобто у виразі |A|+|B|+|C|–|A∩B|–|B∩C|–|A∩C не враховані. Отже, їх треба додати:

|AB|=|A|+|B|+|C|–|A∩B|–|B∩C|–|A∩C|+|A∩B∩C|. (**)

     Вирази (*), (**) наводять на припущення, що в загальному випадку об'єднання n множин , , …,

     |…|=||+||+…+||–||–||–…–||+

     +||+…+||–…+|… |. (1)

     Як бачимо, кількості елементів усіх можливих перетинів непарної кількості множин додаються, а парної – віднімаються. Формула (1) називається формулою включень і виключень. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

РОЗДІЛ 2. Методи розв’язання комбінаторних

олімпіадних задач 

     1. Метод рекурентних  співвідношень. 

     Метод рекурентних співвідношень полягає  в тому, що рішення комбінаторної  завдання з n предметами виражається  через рішення аналогічної задачі з меншою кількістю предметів  за допомогою деякого співвідношення, яке називається рекурентних. Користуючись цим співвідношенням, шукану величину можна обчислити, виходячи з того, що для невеликої кількості предметів  рішення задачі легко знаходиться.  

     2. Метод включення  і виключення.

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

     Наприклад, у випадку двох множин A, B формула включень-виключень має вигляд: |AB|=|A|+|B|-|A B|

     У сумі | A | + | B | елементи перетину A B враховано двічі, і щоб компенсувати це ми віднімаємо |AB| з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, що наведена на малюнку праворуч. Таким же чином і в разі n> 2 множин процес знаходження кількості елементів об'єднання полягає у включенні за все, потім виключення зайвого, потім включення помилково виключеного і так далі, тобто в поперемінному включенні і виключення. Звідси і відбувається назва формули.  
 
 

     3. Метод траєкторій.

     Для багатьох комбінаторних задач можна  вказати таку геометричну інтерпретацію, що зводить задачу до підрахунку числа  шляхів (траєкторій), що володіють певною властивістю. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

РОЗДІЛ 3. Приклади розв’язання комбінаторних

     олімпіадних задач 

     ЗАДАЧА  63.

     Розв’язання І. Підрахуємо, скільки чотиризначних чисел з неповторним цифрами можна скласти з цифр 1, 2, ..., 9. Першу цифру c1 можна вибрати дев'ятьма способами. Після того як з1 визначена, другий цифру с2 можна вибрати вісьмома способами. Поставивши перші дві цифри с1 і с2 ми зможемо вибрати третю цифру с3 сім'ю способами, а після того, як визначені перші три цифри с1, с2, с3, останньою цифрою с4 можуть виявитися ще 6 цифр. таким чином, множина всіх допустимих чисел містить 9 × 8 × 7 × 6 елементів.

     Для будь-якого числа, що належить цій  безлічі, у тому ж безлічі існує  цілком певний число, кожна цифра якого доповнює відповідну цифру вихідного числа до 10. Таким чином, всі числа безлічі можна розбити на пари, об'єднавши в одну пару числа, у яких цифри, які стоять на одному і тому ж місці, в сумі дають 10, наприклад 3562 і 7548.

     Усього  є (1 / 2) × 9 × 8 × 7 × 6 таких пар. Сума чисел, що утворюють одну пару, дорівнює 1000 × 10 +100 × 10 +10 × 10 +10 =11110. Отже, сума всіх членів, що утворюють що розглядається безліч, дорівнює

       × 9 × 8 × 7 ×  6 × 11110 = 16798320.

     Розв’язання ІІ. Як підраховано в І вирішенні, всього існує 9 × 8 × 7 × 6 допустимих чисел. Стільки ж цифр припадає на кожен десятковий розряд цих чисел. У будь-якому десятковому розряді кожна з дев'яти цифр зустрічається однакову кількість разів, а саме (9 × 8 × 7 × 6)/ 9 = 8 × 7 × 6 разів. Отже, сума цифр, що стоять у будь-якому десятковому розряді, дорівнює

     8 × 7 × 6 (1 +2 +3 +4 +5 +6 +7 +8 +9) = 8 × 7 × 6 × 45, а сума всіх чисел –  8 × 7 × 6 × 45 × 1111 = 16798320. 

     ЗАДАЧА  69.

     Нехай F (n) - кількість способів, якими можна  вкласти n листів в n конверти, ... конверт так, щоб жоден лист не потрапив у «свій» конверт . Потрібно обчислити F (6).

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

       Припустимо, що, переплутавши листи  і конверти, ми вклали лист  в конверт (i ≠ 1). Можливі два випадки:

     а) Лист потрапив в конверт . Тоді інші 4 листа (помилково) вкладені в 4 інших конверта, що можна зробити F(4) способами. Оскільки може бути будь-яким з п'яти конвертів , то розкласти 6 листів по шести конвертам так, щоб лист потрапило в конверт (i ≠ 1), лист - у конверт і інші листи також опинилися в "чужих" конвертах, нам вдасться 5×F(4) способами.

     б) Лист не потрапило в конверт . Умовимося на хвилину вважати, що лист повинен бути відправлений у конверті . Тоді ні один з листів не потрапило в "свій" конверт. Розкласти в повному безпорядку 5 листів по п'яти конвертів можна F(5) способами, а , як і раніше, може бути будь-яким з п'яти конвертів. Отже, розкласти 6 листів по шести конвертам так, щоб відіслати листа в конверт (i ≠ 1), лист не потрапило в конверт і інші листи також опинилися в "чужих" конвертах, нам вдасться 5 × F(5) способами.

     Оскільки  випадки (а) і (б) вичерпують всі можливі варіанти помилкового розподілу листів по конвертах, то

     F(6) = 5F(5) + 5F(4).

     Аналогічно

     F(5) = 4F(4) + 4F(3),

     F(4) = 3F(3) + 3F(2),

     F(3) = 2F(2) + 2F(1).

     Оскільки  зрозуміло, що

     F(1) = 0 , F(2) = 1,

     то  наведені вище співвідношення дозволяють послідовно обчислити 

                 F(3) = 2, F(4) = 9, F(5) = 44, F(6) = 265.

     Примітка. У рішенні задачі 69 число 6 не має особливого значення. Всі міркування залишаються в силі і в загальному випадку при довільному число N N листів і конвертів. Повторюючи їх, ми отримаємо співвідношення

     F(n) = (n-1)F(n-1) + (n-1)F(n-2).       (1)

     Це  так звані зворотні, або рекурентні, співвідношення, що дозволяють обчислити F(n) за відомими значеннями F(n-1) і F(n-2).

     Співвідношення  (1) разом з початковими значеннями F(1) =0, F(2) = 1 дозволяють знайти залежність F(n) від n наступним чином. Запишемо співвідношення (1) у вигляді

       F(n) – nF(n-1) = -,     (2)

звідки  видно, що різниця F(k) – kF(k-1) при будь-якому натуральному k > 1 має одну і ту саму абсолютну величину, але змінює знак при переході від k до k+1. Оскільки F(2) – 2F(1) = 1, тоді

     F(n) – nF(n-1) = ,  (n > 1).    (3)

     Із  співвідношення  (3) слідує, що

       – = .     (4) 

     Введемо нове позначення

     φ(n) = ,

     Запишемо  співвідношення (4) у вигляді:

     φ(n)- φ(n-1)= .

     Аналогічно

     φ(n-1)- φ(n-2)=,

     …………………………

     φ(2)- φ(1)=.

     Додаючи окремо ліві і праві частини виписаних  співвідношень і враховуючи, що φ(1)=, отримаємо:

     φ(n)=.

     Таким чином,

     F(n)=n![.

     Розв’язана нами задача називається задачею Бернулі-Ейлера про спутані листи. 

     ЗАДАЧА 74.

     Відповідь на запитання задачі залежить від  того, чи будемо ми включати в кількість  підмножин порожню множину (тобто  множину, яка не містить жодного  елементу) або ні. В першому випадку (порожня множина входить в  число підмножин) відповідь на 1 більше, ніж в другому. Домовимося розглядати лише не порожні підмножини.

     Нехай p – число всіх можливих розбиттів множини Z, яка містить n елементів, на двох не порожніх підмножинах. Тоді 2p означає число всіх підмножин множини Z, не порожніх й відмінних від самої множини Z.

     Число 2p ми знайдемо як суму числа підмножини, яка містить 1, 2, ….., (n-1) елементів. Оскільки підмножин, які містять k елементів, існує стільки ж, скільки варіантів вибрати k елементів із n, тобто, то

     2p=.                                                (1)

     За  формулою бінома Ньютона отримаємо

     .               (2)

     Віднявши  від рівності (2) рівність (1) і враховуючи, що , отримаємо , звідки p=  .        

     ЗАДАЧА 104     

     Позначимо присутніх в залі Нехай M – множина {}, N – множина {} і P – множина {}. Випадок, про який сказано в задачі, можна представити, наприклад, якщо кожен із тих, хто входить в множину M, знайомий з тими і лише з тими, хто входить в множину N або в множину P (всього 67 чоловік), і аналогічно кожен з тих, хто входить в множину N,знайомий з тими і лише з тими, хто входить в множини P і M (всього 67 чоловік), а кожний з тих хто включений множину P, знайомий з тими і лише з тими, кого ми віднесли до множин M і N (всього 66 чоловік). Дійсно, якщо () – будь які 4 чоловіка із числа присутніх у залі, то 2 із них завідомо входять в одну й ту ж множину M, N або P і тому не знайомі один з одним. Отже, твердження задачі доведено.