Регистрирайте се
Предишната тема :: Следващата тема |
Автор |
Съобщение |
Мирослав Стоенчев Напреднал
Регистриран на: 21 Aug 2007 Мнения: 279
гласове: 45
|
Пуснато на: Sat Oct 06, 2007 9:04 pm Заглавие: Комбинаторика |
|
|
Тук ще бъдат изложени основни факти от Комбинаториката улесняващи подготовката за състезания.
|
|
Върнете се в началото |
|
|
Реклама
|
Пуснато на: Заглавие: Реклама |
|
|
|
|
Върнете се в началото |
|
|
Nona Напреднал
Регистриран на: 12 Sep 2006 Мнения: 477
гласове: 163
|
Пуснато на: Mon Oct 08, 2007 2:39 pm Заглавие: |
|
|
Description: |
|
Големина на файла: |
40.88 KB |
Видяна: |
5553 пъти(s) |
|
|
|
Върнете се в началото |
|
|
Nona Напреднал
Регистриран на: 12 Sep 2006 Мнения: 477
гласове: 163
|
Пуснато на: Mon Oct 08, 2007 2:42 pm Заглавие: |
|
|
Description: |
|
Големина на файла: |
44.94 KB |
Видяна: |
5552 пъти(s) |
|
Description: |
|
Големина на файла: |
40.83 KB |
Видяна: |
5552 пъти(s) |
|
Description: |
|
Големина на файла: |
10.77 KB |
Видяна: |
5552 пъти(s) |
|
|
|
Върнете се в началото |
|
|
Мирослав Стоенчев Напреднал
Регистриран на: 21 Aug 2007 Мнения: 279
гласове: 45
|
Пуснато на: Mon Oct 08, 2007 9:29 pm Заглавие: |
|
|
Теорема(Шпернер). Нека n е естествено число и А е фамилия от подмножества на множеството {1,2,...,n} така, че никой елемент на А не се съдържа в друг елемент на А.
Тогава max|A|=Ckn , където к=[n/2].(тук под Ckn=n!/k!(n-k)! разбираме съответния биномен коефициент)
Д-во: Да разгледаме множеството на всички вериги Т от вида Т1,Т2,...,Т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)! вериги от Т, т.е.
Ai=Тki и съответните вериги с участието на Тki-фиксирано с ki на брой елемента са:
Т1,...,Тki-1,Тki,Тki+1,...,Тn.
Както казахме елементите на Ai=Тki са фиксирани и са ki на брой. Тогава Тki+1 съдържа Тki и има с един елемент повече, този елемент можем да го изберем по n-ki начина.Аналогично Тki+2 съдържа Тki+1 и има с един елемент повече, който можем да го изберем n-ki-1 начина, и т.н. частта от веригата Тki+1,Тki+2,...,Тn може да се избере по (n-ki)(n-ki-1)...2.1=(n-ki)! начина.
Аналогично частта Т1,Т2,...,Тki-1 от Т при фиксирано Ai=Тki може да се избере
по ki! начина.Наистина Тki съдържа точно ki елемента,Тki-1 се различава от Тki с това че е подмножество на Тki и има един елемент по-малко, тогава броя на начините по които можем да получим Тki-1 от Тki като премахнем един елемент е ki. Аналогично Тki-2 може да се избере по ki-1 начина и т.н., Т1 може да се избере по 2 начина. Значи броя на начините
по които може да изберем веригата Т(i) = Т1,Т2,...,Тki-1,Тki+1,...,Тn-1,Тn
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
гласове: 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]
|
|
Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми Не Можете да отговаряте на темите Не Можете да променяте съобщенията си Не Можете да изтривате съобщенията си Не Можете да гласувате в анкети You cannot attach files in this forum Може да сваляте файлове от този форум
|
|