Opis
Słuchaliście kiedyś jak grają ciągi? Kolorowaliście grafy ze złośliwym malarzem? A może byliście kiedyś na kole podbiegunowym diamentu Azteków? Nie? To może najwyższa pora! ;)
Program zajęć
W pierwszy dzień udowodnimy znane twierdzenia teorii grafów. M. in. twierdzenie Halla, Orego, twierdzenia o kolorowaniu (Koniga, Vizinga etc.), i zrobimy trochę mniej znanych i trochę trudniejszych (niż zadania kwalifikacyjne) zadań. W drugi przedstawię różne mniej ortodoksyjne zagadnienia: ciągi np. Thuego, EKG, problemy typu Dot-town suicides, diament Azteków, problem samotnego biegacza. Trzeci dzień będzie zależał od tego, jaką tematyką będą zainteresowani słuchacze. Mogą to być przykładowo warianty kolorowanie grafów (np. kolorowanie z list czy Mr. Paint and Mrs. Correct).
Wymagania
W zasadzie nie ma jakichś szczególnych wymagań, wystarczą podstawowe pojęcia (czyt. wiedza np. co to jest graf mile widziana) i umiejętność kombinowania.
Zadania kwalifikacyjne
1. Dany jest graf pełny. Każdą jego krawędź malujemy losowo na czerwona bądź niebiesko. Uzasadnić, że krawędzie koloru czerwonego lub krawędzie niebieskiego tworzą graf spójny.
2. Dwa misie dostają czapeczki w kolorach: czerwonym lub niebieskim (losowo). Każdy z misiów widzi czapeczkę drugiego misia, ale nie widzi swojej. Misie mają napisać na karteczce kolory i jeżeli któryś z nich zgadnie, jaki kolor ma czapeczka na jego głowie, to misie wygrywają. Wcześniej mogą się umówić odnośnie strategii, ale po zobaczeniu czapeczek nie mogą już porozumiewać się ze sobą w żaden sposób. Jaką strategię powinny zastosować misie?
3. Udowodnić, że wszystkie podzbiory zbioru skończonego można ustawić w ciąg, którego kolejne wyrazy różnią się jednym elementem.
4. Ile jest funkcji f: {1,…,n}->{1,…,n} monotonicznych (czyli spełniających warunek f(i)<=f(j) dla i<j)?
5. Odbywa się przyjęcie u państwa Szaradków, w którym oprócz Pana Szaradka i Pani Szaradkowej biorą udział cztery inne pary. ludzie wymieniają uściski dłoni między sobą, przy czym żadne dwie osoby nie robią tego dwa razy i nikt nie wita się ze swoim patnerem/partnerką. Zarówno Pan jak i Pani domu wymienili z kimś z gości co najmniej po jednym uścisku. Pod koniec przyjęcia Pan Szaradek zapytał każdego (wyłączając siebie) o liczbę dokonanych uścisków. W odpowiedzi każda z osób podała inną liczbę. Ile uścisków dokonała Pani Szaradkowa?
6. W pewnej grupie chłopców i dziewcząt każda dziewczyna zna dokładnie k chłopców i każdy chłopiec zna dokładnie k dziewcząt. Zakładamy, że relacja znajomości jest symetryczna. Czy zawsze jest możliwe skojarzenie par małżeńskich tak, aby każda z dziewcząt wyszła za mąż za chłopca, którego zna?
Proponowany próg: 4/6 zadań.
Przydatne linki:
http://dl.dropbox.com/u/3899218/md-grytczuk.pdf
http://mediawiki.ilab.pl/index.php/Matematyka_dyskretna_1
http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_2