Комбинаторна математика2020
Миню Балкански
На тази страница са събрани описанията на всеки от курсовете. Препоръки за избора между тях можете да намерите тук.
Курсовете се уточняват.
Методът на пълната математическа индукция е един от ключовите похвати в математиката и показва нейната красота и сила. Състои се от две части – да покажем, че дадено твърдение е вярно за някое число (така наречената База на индукцията
) и след това да покажем, че ако твърдението е вярно за някое число, то е вярно и за следващото (така наречената Индукционна стъпка
). Целта на лекцията е участниците да се запознаят с прилагането на метода, и да започнат да забелязват типовете задачи, в които той може да помогне.
Никакви.
1
Граф е математическа мрежа, която може да бъде използвана да опише пътната мрежа, Интернет, познанства между хора и др. Ще се запознаем с основни понятия от теория на графите като връх, ребро, път, цикъл и много други. Първата лекция ще завърши с въвеждане на граф-дървета и техните свойства. Основна част от втората лекция ще бъде посветена на Ойлерови и Хамилтонови пътища и цикли. Третата лекция ще се занимае със свойствата на планарните графи.
Знания от Увод в индукцията.
1, последната лекция е подходяща и за ниво 2
Защо една квадратна таблица 41x41 не може да бъде запълнена изцяло с домина? Инвариант е брой обекти в дадена задача, който остава непроменен или се променя закономерно от началото до края. Когато открием кои обекти да броим, можем да направим заключения, които често водят до решение на задачата.
Никакви.
1
Рекурентно зададена редица, е редица, в която всеки нов член се получава чрез аритметични действия от предишните (най-известната такава редица е тази на Фибоначи). Фокусът на лекцията ще е върху намирането и доказването на рекурентни връзки, които да помогнат при решаването на задачата за конкретни числа.
Никакви.
1
Двама души играят следната игра...
– толкова пъти сме го чували. Ще говорим за намирането на правилна стратегия в игрите с двама играчи, фокусирайки се най-вече върху печеливши и губещи позиции.
Никакви, но на участниците може да е полезно да видят как могат да приложат знанията си от Увод в инвариантите в задачите от игри и стратегии.
1
Ще разгледаме задачи, свързани с покрития на дъски с плочки в различни форми.
Познания по инварианти, например от Увод в инвариантите.
1
Ще разглеждаме по-сложни задачи, свързани с индукция и такива, в които не е очевидно къде и как тя трябва да се приложи. Ще завършим с методът „Ретроградна индукция“, където правим индукционна стъпка за непоследователни числа, а след това „запълваме дупките“.
Участниците трябва да са добре запознати със знанията от Увод в индукцията.
2
Тук ще разгледаме по-сложни игри от Увод в игрите и стратегиите. В игрите ще може да има повече играчи, а стратегиите ще са доста по-неконвенционални. Ще разгледаме известната задача за пиратите и съкровището (като се опитаме да я генерализираме), както и други популярни задачи от математическия фолклор.
Никакви.
2
На колко части можем да разделим една торта с n разреза? Това е пример на задача от областта на комбинаторната геометрия. В тази лекция ще се запознаем с теоремата на Хели и няколко нейни приложения. Например ще докажем, че ако за n точки в равнината всеки три се съдържат в кръг с радиус 1, то всичките n точки се съдържат в кръг с радиус 1.
Никакви.
2
Ще разгледаме задачи, в които (чрез малко хитрост) можем да достигнем до алгебрични тъждества чрез кратки и елегантни комбинаторни разсъждения.
Боравене с елементарни алгебрични изрази (например умножение на многочлени) е полезно, но не и строго задължително.
2
Заглавието издава материала: ще оцветяваме графи (по върхове и по ребра). Ще търсим резултати от рода на Колко цвята ни трябват, за да няма две съседни едноцветни неща
. Ще започнем от най-общи резултати в първата лекция, във втората ще разгледаме теоремата на Визинг, а третата ще е посветена на теореми на Рамзи.
Базови понятия от теория на графите, както са представени например в Увод в теория на графите, въпреки че ще напомним необходимата терминология. Знания от Увод в индукцията. Полезно е да сте се виждали използване на броенето по два начина, но, разбира се, не е необходимо познаването на Броене по два начина и комбинаторни тъждества.
2, последната лекция е подходяща и за ниво 3
Този курс е въведение в екстремалната теория на графите. Най-общо тя се занимава с въпроси от вида колко най-голям (или най-малък) може да е даден параметър на граф с определено свойство
. По време на първата лекция ще въведем основните понятия и ще разгледаме подробно теоремата на Дирак, в която свойството е липсата на Хамилтонов цикъл, а параметърът е най-ниската степен на върх в графа. Втората лекция е посветена на теоремата на Туран и свързани с нея резултати. В тази теорема свойството е липсата на определени подграфи (например триъгълници), а параметърът е броят ребра в графа.
Базови понятия от теория на графите, както са представени например в Увод в теория на графите, въпреки че ще напомним необходимата терминология. Знания от Увод в индукцията.
2-3
На колко части можем да разделим една торта с n разреза? Това е пример на задача от областта на комбинаторната геометрия. В първата лекция ще се запознаем с теоремата на Борсук-Улам в равнината и в триизмерното пространство и няколко нейни приложения. Втората лекция ще започне с доказване на теоремата на Силвестър: ако в равнината са дадени n точки, които не лежат на една права, то има права, която съдържа точно две от дадените точки. Основна част от лекцията ще бъде посветена на теоремата на Моцкин-Рабин, която обобщава теоремата на Силвестър, разглеждайки точки от два различни цвята.
За доказване на теоремата на Моцкин-Рабин е силно препоръчително познаване на основните свойства на полюса и полярата.
3
Сдвояване на граф е покриване на върховете му с (две по две) непресичащи се ребра. Ще се съсредоточим предимно върху двуделните графи. През първите две лекции ще се занимаем с Теоремата на Хол, няколко нейни еквивалентни формулировки и техни приложения. В третата лекция ще разгледаме алгоритмични аспекти на сдвояванията, по-точно унгарския алгоритъм за намиране на сдвояване, и, ако времето позволи, на стабилните сдвоявания.
Базови понятия от теория на графите, както са представени например в Увод в теория на графите, въпреки че ще напомним необходимата терминология. Базови понятия и означения от теория на множествата. Знания от Увод в индукцията. На места полезни, но не и необходими могат да бъдат знания от Оцветяване на графи.
3
Подмножествата на числата от 1 до n могат да се представят по естествен начин чрез граф. През първата лекция ще се запознаем с това представяне и ще разгледаме лемата на Шпернер. Втората лекция е посветена на изопериметрични неравенства, т.е. резултати отговярящи на въпроса При даден обем колко най-малка може да бъде повърхността на множество?
или иначе казано Защо сапунените мехури са кръгли?
Базови понятия от теория на графите, както са представени например в Увод в теория на графите. Базови понятия и означения от теория на множествата. Знания от Увод в индукцията. По възможност, теорема на Хол (или Фробениус), напр. от Сдвоявания, но не е задължително, тъй като тя ще бъде припомнена и ще се използва само веднъж.
3
Ще докажем една централна теорема от теория на графите и ще разгледаме нейни приложения, например за доказване на теоремата на Хол, която ще бъде разгледана и в Сдвоявания.
Базови понятия от теория на графите, както са представени например в Увод в теория на графите. Знания от Увод в индукцията.
3
Може да сте виждали твърдението, че ако оцветим върховете на пълен граф с 6 върха в два цвята, винаги има едноцветен триъгълник. Ще обобщим този факт. В първата лекция ще видим основни теореми на Рамзи, а по време на втората ще се занимаем с по-изискани резултати, като например теория на Рамзи върху безкрайни графи и др.
Базови понятия от теория на графите, както са представени например в Увод в теория на графите. Да сте на "ти" с резултатите от Увод в индукцията.
3