[an error occurred while processing this directive]

Kombinatorický seminář

V letním semestru 2004/2005 se seminář koná pravidelně (modulo svátky) ve středu od 9:00 v posluchárně S3. Seminář vedou Martin Mareš a Robert Šámal.

Kombinatorický seminář (DMI022) je seminář pro studenty 2.-5. ročníku, zaměřený na řešení jednoduchých (ale často dosud nevyřešených) úloh z kombinatoriky a příbuzných oborů, jako je třeba teorie grafů a kombinatorická geometrie. Podstatnou součástí semináře je rovněž četba a referování odborných článků účastníky semináře. Každoročně je pro studenty Kombinatorického semináře pořádána Jarní škola kombinatoriky.

Program

2. 3.Honza HladkýCover Pebbling Theorem
9. 3.Rudolf StolařPatnáctka
16. 3.Lukáš BernardickýSkoky koněm
23. 3.Josef CibulkaPermutace se zakázaným vzorem
30. 3.Marek TesařRozklady kvádru
6. 4.Martin CetkovskýPopulární párování
13. 4.Jan KynčlOrientovaná vnorení (pokr.příště)
20. 4.Jan KynčlOrientovaná vnorení (dokončení)
27. 4.Tomás GavenčiakKoncový Nim
4.5. a 11.5.jarní škola---seminář se nekoná
18.5.Tomáš VyskočilZakázané podmatice alias Stanley-Wilfova domněnka
25.5.Tomáš VallaHravá verze van der Waardenovy věty

Úloha na tento týden

Tento semestr budeme společně řešit problémy z knihy pana Lovásze: Combinatorial problems and exercises. Na konci jednoho semináře si řekneme zadání, na začátku příštího někdo, kdo problém vyřešil, řekne řešení. Tady na webu se kromě zadání dočtete i malou nápovědu.

Zadání: Máme několik přirozených čísel, jejich bitový xor je nenulový. Dokažte, že lze jedno z nich zmenšit (a ostatní nechat) tak, aby bitový xor získaných čísel byl nulový.

Odtud plyne řešení hry Nim: hru hrají dva hráči s několika hromádkami zápalek. Tah spočívá v odebrání libovolného počtu zápalek z jedné z hromádek, kdo nemůže táhnout, prohrál. Shora uvedené tvrzeníčko je nejtěžší část důkazu toho, že hra je vyhraná pro prvního hráče právě tehdy, když xor počtu sirek na jednotlivých hromádkách je nenulový.

Nápověda

Minulé úlohy

Články k referování

Časem se tu objeví v přehlednější formě, zatím jen takto. Nenechte se zmást tím, že jich tady je víc, než jsme předvedli na semináři.

Historie semináře

Zimní semestr [an error occurred while processing this directive]