Міністерство освіти і науки України

Полтавський державний педагогічний

університет ім.В.Г. Короленка 

                                                                               Кафедра математики        

Курсова робота на тему: 
 

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

                                                 Виконала:

                                                      студентка групи М-42

                                                    фізико-математичного

                                                    факультету 

                                                 Науковий керівник:

                                                    старший викладач

                                                    Севрюк  І.В. 
 
 
 
 
 
 

Полтава 2009

     Зміст. 

ВСТУП .....................................................................................................................3

РОЗДІЛ 1. Елементи комбінаторики……………………….................................5

          1.1. Загальні зауваження………………………………………………...…5

1.2.  Принцип добутку і принцип суми……………….………..………....5

1.3. Розміщення з повтореннями..................................................................6

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

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

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

1.7. Комбінації з повтореннями…………………………………………...7

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

Розділ 2. Методи розв’язання комбінаторних олімпіадних задач………….10

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

ВИСНОВОК ..........................................................................................................26

СПИСОК  ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ..............................27 

     Вступ 

     Актуальність теми.

     Комбінаторика — важливий інструмент для підготовки до формування ймовірнісного мислення учня.

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

     Але це знайомство може відбуватися набагато раніше, ніж у 10 — 11 класі і більш природнішим шляхом. Важливо максимально поєднати принципи доступності та науковості у вивченні такого напрочуд цікавого та розвиваючого розділу математики, як комбінаторика.

     Довгий  час здавалося, що комбінаторика  лежить поза основної течії розвитку математики та її застосувань. Хід справ  різко змінився після появи ЕВМ  та пов’язаним з цим розквіту кінцевої математики. Зараз комбінаторні методи застосовуються в теорії випадкових процесів, статистиці, математичному  програмуванні, обчислювальній математиці, плануванні експериментів і т.д. В математиці комбінаторика використовується при вивченні кінцевих геометрій, комбінаторної  геометрії, представлень груп, неасоціативних алгебр і т.д. 

     Мета роботи. Метою роботи є розробка олімпіадних задач з комбінаторики і їх адаптація, з урахуванням особливостей області, існуючих математичних моделей задач з комбінаторики. 

Задачі  дослідження.

1. Аналіз навчальної літератури, розгляд елементів комбінаторики.
2. Сформувати уявлення про правильне розв’язання олімпіадних задач з комбінаторики.
3. Розв’язання задач за принципами комбінаторики.
4. Охарактеризувати такі здачі з допомогою елементів комбінаторики.
5. Розвинути уміння і навички у розв’язанні олімпіадних задач з комбінаторики.

Об’єкт дослідження: олімпіадні задачі в комбінаториці. 

Предмет дослідження: методи розв’язання оліпіадних задач. 

Застосовані методи:

• теоретичний аналіз наукової літератури, з розглядом олімпіадних задач з комбінаторики;
• синтез необхідних відомостей про олімпіадні задачі;
• узагальнення і систематизація отриманих знань.

Особистий внесок:

     Проаналізувала, узагальнила і систематизувала  наукову та навчальну літературу  в якій розкривалися поняття і сутність розв’язків олімпіадних задач з комбінаторики. 
 
 
 
 
 
 

     РОЗДІЛ 1. Елементи комбінаторики. 

1. Загальні  зауваження.

     Комбінаторика у класичному розумінні (сучасна назва – комбінаторний аналіз) – це розділ математики,присвячений розв’язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами. Ці правила визначають спосіб побудови деякої конструкції – комбінаторної сполуки (конфігурації). Вивчати властивості цих сполук та підраховувати кількість різних способів їх побудови зручно у такій послідовності:

1. спочатку формулюється  класична (ключова) задача, яка приводить до комбінаторної конфігурації, що вивчається;
2. потім наводиться розв’язання цієї задачі та виведення основної формули;
3. після цього будується математична модель комбінаторної сполуки і мовою теорії множин дається її точне означення.

     В основі класичної комбінаторики  лежать принцип суми та принцип добутку. 

2. Принцип добутку і принцип  суми.

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

     Принцип суми:

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

     Принцип добутку:

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

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

3. Розміщення  з повтореннями.

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

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

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

     Означення. Розміщення по m елементів n-елементної множини A, де m × n – це послідовність елементів множини A, що має довжину 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!. Отже, n × n = n!. 

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

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

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

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

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

     Приклад. Нехай m різних кульок розкладаються по n різних ящиках так, що в першому ящику кульок, у другому – кульок, …, у n-му – k×n кульок, причому m=++…+. Пронумеруємо кульки від 1 до m, ящики – від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру кульки номер ящика, куди вона потрапила. Отже, маємо послідовність довжини m=++…+, в якій номери 1, 2, …, n повторюються , , …, разів відповідно. Очевидно, що така функція відповідає розкладу кульок взаємно однозначно. Таким чином, розклад подається як перестановка з повтореннями складу (, , …, ).

     Наведені  неформальні міркування демонструють зв'язок між перестановками й розміщеннями з повтореннями та обгрунтовують формулу:

     n×m. 

7. Комбінації  з повтореннями.

     Комбінації  елементів якоїсь множини – це її підмножини. Але у множинах елементи не повторюються, тому термін "комбінації з повтореннями", що склався в  математиці, не можна вважати вдалим.

     Множина перестановок розбивається на класи еквівалентності, які взаємно однозначно відповідають усім можливим складам (, , …, ). Кожний такий клас еквівалентності й називається комбінацією по m елементів з повтореннями складу (, , …, ).

     Можна означити комбінації з повтореннями дещо інакше. Серед усіх еквівалентних  перестановок складу (, , …, ) є перестановка вигляду

     (, , …, , , , …, , …, , , …, ).

     14243 14243 14243

       …

     Приклад. При 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 і тому не знайомі один з одним. Отже, твердження задачі доведено.