Регистрирайте сеРегистрирайте се

Комбинаторика


 
   Форум за математика Форуми -> Теория свързана с олимпиади
Предишната тема :: Следващата тема  
Автор Съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sat Oct 06, 2007 9:04 pm    Заглавие: Комбинаторика

Тук ще бъдат изложени основни факти от Комбинаториката улесняващи подготовката за състезания.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Mon Oct 08, 2007 2:39 pm    Заглавие:

Smile


Събития и действия с тях.gif
 Description:
 Големина на файла:  40.88 KB
 Видяна:  5553 пъти(s)

Събития и действия с тях.gif


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Mon Oct 08, 2007 2:42 pm    Заглавие:

Smile


Вероятности.gif
 Description:
 Големина на файла:  44.94 KB
 Видяна:  5552 пъти(s)

Вероятности.gif



Съединения без повторения.gif
 Description:
 Големина на файла:  40.83 KB
 Видяна:  5552 пъти(s)

Съединения без повторения.gif



Нютонов бином.gif
 Description:
 Големина на файла:  10.77 KB
 Видяна:  5552 пъти(s)

Нютонов бином.gif


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Mon Oct 08, 2007 9:29 pm    Заглавие:

Теорема(Шпернер). Нека n е естествено число и А е фамилия от подмножества на множеството {1,2,...,n} така, че никой елемент на А не се съдържа в друг елемент на А.
Тогава max|A|=Ckn , където к=[n/2].(тук под Ckn=n!/k!(n-k)! разбираме съответния биномен коефициент)

Д-во: Да разгледаме множеството на всички вериги Т от вида Т12,...,Тn, като |Тi|=i, Тi е подмножество на Тi+1, за всяко i=1,2,...,n-1.
Броят на веригите е n! понеже 1 елемент на Т1 може да се избере по n-начина, след като е избран този елемент участва в Т2 и 2-рия елемент можем да го изберем по n-1 начина.Тези 2 елемента участват в Т3, а 3-тия елемент на Т3 можем да го изберем по n-2 начина и т.н. Броя на всички вериги от Т е |T|=n!.
Нека А={A1,A2,...,Ar} е търсената фамилия, kъдето Ai не е подмножество на Aj за всеки i,j: 1≤i≠j≤r.
За всяко i от множеството {1,2,...,n},ако |Ai|=ki, то Ai принадлежи на точно ki!(n-ki)! вериги от Т, т.е.
Aiki и съответните вериги с участието на Тki-фиксирано с ki на брой елемента са:
Т1,...,Тki-1kiki+1,...,Тn.
Както казахме елементите на Aiki са фиксирани и са ki на брой. Тогава Тki+1 съдържа Тki и има с един елемент повече, този елемент можем да го изберем по n-ki начина.Аналогично Тki+2 съдържа Тki+1 и има с един елемент повече, който можем да го изберем n-ki-1 начина, и т.н. частта от веригата Тki+1ki+2,...,Тn може да се избере по (n-ki)(n-ki-1)...2.1=(n-ki)! начина.
Аналогично частта Т12,...,Тki-1 от Т при фиксирано Aiki може да се избере
по ki! начина.Наистина Тki съдържа точно ki елемента,Тki-1 се различава от Тki с това че е подмножество на Тki и има един елемент по-малко, тогава броя на начините по които можем да получим Тki-1 от Тki като премахнем един елемент е ki. Аналогично Тki-2 може да се избере по ki-1 начина и т.н., Т1 може да се избере по 2 начина. Значи броя на начините
по които може да изберем веригата Т(i) = Т12,...,Тki-1ki+1,...,Тn-1n
e ki!(n-ki)!.
Значи Ai участва в точно ki!(n-ki)! вериги и никои 2 елемента Ai и Aj не учстват в една и съща верига, в противен случай -би се оказало,че Ai е подмножество на Aj или обратно.
Така показахме,че на всеки елемент Ai на А, i=1,2,...,r съотвестват ki!(n-ki)! на брой вериги във всяка от които участва само Ai.
Значи разбихме веригите в групи по ki!(n-ki)! на брой, и като сумираме по i=1,2,...,r получаваме ∑ki!(n-ki)! = n!, т.е.
∑ki!(n-ki)!/n! = 1 => ∑1/Ckin=1. Нека s=[n/2], тогава Ckin≤Csn, понеже най-голямата стойност на Cjn се достига при j=[n/2].Тогава
1/Csn≤1/Cnki => 1=∑1/Ckin≥∑1/Csn=r/Cns => r≤Csn.
Но ако изберем Ai да са всичките [n/2] елементни подмножества на {1,2,...,n}, то за всеки i,j: 1≤i<j≤r Ai не е подмножество на Aj, нито обратното.Така получихме r≥Csn.
Значи Csn≤r≤Csn =>
max|A|=r =Csn , при s=[n/2]. С това теоремата е доказана.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sun Dec 09, 2007 3:35 pm    Заглавие:

Лема 1. Нека [tex]M[/tex] е крайно равнинно множество от точки, като [tex]|M|\ge3.[/tex] Tогава съществува изпъкнал многоъгълник с върхове в [tex]M,[/tex] който съдържа [tex]M.[/tex]

Лема 2. Измежду всеки [tex]5[/tex] точки в равнината, които са в общо положение, съществуват [tex]4,[/tex] които са върхове на изпъкнал четириъгълник.

Лема 3. Нека [tex]M, |M|=n[/tex] e равнинно множество от точки в общо положение.
Точките от [tex]M[/tex] са върхове на изпъкнал [tex]n-[/tex] ъгълник, тогава и само тогава, когато всеки [tex]4[/tex] точки от [tex]M[/tex] са върхове на изпъкнал четириъгълник.

Теорема(Ердьош-Секереш): За всяко естествено число [tex]n\ge3[/tex] съществува такова естествено число [tex]m,[/tex] че всяко равнинно [tex]m[/tex] - елементно множество от точки в общо положение, съдържа върховете на изпъкнал [tex]n-[/tex] ъгълник.

Дефиниция. Нека [tex]A[/tex] e множество,а [tex]k\in N.[/tex] Ще казваме, че е зададено [tex]k-[/tex] оцветяване на [tex]A,[/tex] ако някои от [tex]k-[/tex] елементните подмножества на [tex]A[/tex] са наречени черни, а останалите [tex]k-[/tex] елементни подмножества - бели.Едно подмножество [tex]B[/tex] на [tex]A,[/tex] наричаме едноцветно(черно или бяло), ако всичките му [tex]k-[/tex] елементните подмножества са оцветени еднакво при това оцветяване.

Теорема(Ремзи): Нека [tex]k,m,n[/tex] са естествени числа, като [tex]m,n\ge k.[/tex]Toгава съществува естествено число [tex]r[/tex] със свойството: ако [tex]|A|=r[/tex] и [tex]\gamma[/tex] e [tex]k-[/tex] оцветяване на [tex]A,[/tex] то в множеството [tex]A[/tex] има [tex]m-[/tex]елментно черно или [tex]n-[/tex]eлементно бяло подмножество при оцветяването [tex]\gamma.[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Теория свързана с олимпиади Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.