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

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

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

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

 
 
 
 
 
 

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

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

                                                 Виконала:

                                                      студентка групи М-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

       …