Každý student musí napsat referát z předmětu Diskrétní matematika sám, žádná spolupráce na textu referátu není dovolena. Je pouze povoleno diskutovat o zadání referátu se spolužáky a položit otázky na cvičeních.

V každém referátu jsou dva příklady, jeden z kombinatoriky, druhý z teorie grafů. Hodnotí se každý příklad 0/3/5 bodů, tj. stylem NE/TÉMĚŘ SPRÁVNĚ/ANO. V případě mimořádně kvalitního řešení příkladu lze udělit i 10 bodů za příklad. Referát vypracujte formou odborného článku: nadpis, jméno, abstrakt a přehledné členění na sekce. Doporučujeme vypracovat referát včetně titulního listu, na kterém budou uvedeny kromě názvu referátu i údaje studenta (jméno, osobního číslo, ...). Bude psán na počítači v rozsahu asi 2 až 5 stran A4. Referát odevzdáváte e-mailem v předepsaném formátu nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k přednesení vašeho referátu během cvičení.

Abstrakt je odstavec shrnující o čem referát je a co je hlavním přínosem vaší práce. Zahrnuje i podstatu zadání. Zadání referátu nekopírujte do výsledného textu, ale vlastními slovy v úvodu popište co jste řešili.

Můžete se podívat na vzorový referát ve formátu pdf: dim_vzorovy_referat.pdf.

Číslo zadání bude studentům přiděleno na cvičení.

Termín odevzdání je 8.12.2008 ve 13:00.

1. Zadání

Kombinatorika
Mějme balíček karet očíslovaných 1, 2, ..., 32. Máme stroječek na míchání karet. Když do stroječku vložíme seřazený balíček v pořadí 1, 2, ..., 32, strojek balíček rozdělí na dvě stejně velké poloviny a tyto pak vmíchá mezi sebe tak, že mezi karty jedné poloviny vmíchá v daném pořadí karty druhé poloviny. Karty z každé poloviny se nemusí pravidelně střídat, navíc po každém vložení do stroječku můžeme dostat jiné vmíchání, ale vždy zůstane zachováno pořadí karet v obou polovinách. Ukažte, že existuje takové rozmíchání balíčku karet, které nemůžeme dostat po nejvýše čtyřech mícháních ve stroječku.

Teorie grafů
Máme dán konvexní n-úhelník a v něm všechny úhlopříčky. Žádné tři úhlopříčky se neprotínají v jednom bodě (uvnitř n-úhelníka). Vypočítejte počet oblastí uvnitř n-úhelníka, které takto vzniknou.
Návod: Využijte Eulerův vzorec a další známá tvrzení z teorie grafů.

2. Zadání

Kombinatorika
Na stole leží n² koláčků uspořádaných do pravidelné sítě (n řad po n koláčcích), kde n≥2. Koláček v levém horním rohu je otrávený. Dva hráči střídavě jedí koláčky a ten, který sní otrávený koláček, prohrál. V každém tahu vezme hráč některý koláček a sní jej společně se všemi koláčky, které se nachází napravo a dolů od vybraného koláčku. Kdyby například vybral koláček v páté řadě a čtvrtém sloupci, tak sní celkem (n-4)(n-3) koláčků. Ukažte, že hra není spravedlivá a první hráč může vždy vyhrát.

Teorie grafů
V jedné ostrovní zemi mají celé území rozdělené na čtyři sta dvacet jedna usedlostí tak, že všechny hranice každé usedlosti jsou silnice a jiné silnice v této zemi nejsou. Je známo, že na ostrově nejsou mosty a pouze tři křižovatky, kde se potkává pět silnic, a všechny ostatní křižovatky jsou tvaru X nebo T. Dále víme, že křižovatek ve tvaru T je o sto jedenáct více než tvaru X a že podél celého pobřeží vedou cesty. Kolik je v této ostrovní zemi silnic?

3. Zadání

Kombinatorika
Kolik různých anagramů, které neobsahují slovo ANNA, vznikne ze slova ANAKONDA? Zdůrazněme, že písmena slova ANNA nemusí následovat bezprostředně po sobě. Tedy jak anagram "a A d k N o N A", tak anagram "o k d A N N A a" slovo ANNA obsahuje! Své řešení zdůvodněte!

Teorie grafů
Máme šachovnici o rozměru 3×4 políčka. Na šachovnici postavíme čtyři jezdce (koně), dva bílé a dva černé. Máme prohodit postavení černých a bílých jezdců. Ukažte, že tato úloha je řešitelná pro libovolné rozestavení jezdců.
Návod: Problému můžeme přiřadit graf tak, že jeho vrcholy jsou jednotlivá políčka šachovnice a dva vrcholy jsou spojeny hranou právě tehdy, když mezi odpovídajícími políčky existuje regulérní tah jezdcem.

4. Zadání

Kombinatorika
Nakresleme n, n≥3, přímek v rovině tak, že každé dvě jsou různoběžné a žádné tři se neprotínají v jednom bodě. Dokažte, že počet částí, na které je rovina rozdělena těmito n přímkami, je přesně n(n+1)/2 + 1. Doporučujeme použít matematickou indukci!

Teorie grafů
Na večírku je 25 lidí. Každá dvojice zná dohromady všech ostatních 23 lidí. Lze tyto lidi rozesadit kolem kulatého stolu tak, že každý sedí mezi svými známými? POZOR! Zde chápeme relaci "býti známý s" jako symetrickou relaci, tedy zná-li se x s y, tak y se zná s x.
Návod: Ke každé takové situaci umíte sestavit graf, kde vrcholy jsou jednotliví lidé na večírku a hrana mezi vrcholy x a y je přesně tehdy, když x zná y. Máte ukázat, že každý takový graf obsahuje cyklus, který prochází všemi vrcholy grafu.

5. Zadání

Kombinatorika
Uvažme pravidelný n-úhelník, n≥4. Rozdělme ho diagonálami na trojúhelníky tak, aby měl každý trojúhelník s naším n-úhelníkem společnou alespoň jednu stranu a žádné dvě diagonály se neprotínaly (vytvoříme triangulaci). Ukažte, že každá triangulace obsahuje n-2 trojúhelníků, přičemž právě dva z nich mají s naším n-úhelníkem dvě společné strany.

Teorie grafů
Čtrnáct fotbalových družstev je rozděleno do dvou divizí. Družstva v divizi A označíme A₁, A₂, ..., A₇ a družstva v divizi B označíme B₁, B₂, ..., B₇. Ukažte, že lze naplánovat turnaj těchto družstev tak, že každý z divize A bude hrát s každým z divize B během sedmi dnů, přičemž každé družstvo bude hrát každý den jeden zápas. Alespoň jedno takové rozlosování najděte, tzn. předložte seznam zápasů, které se odehrají v pondělí, v úterý, ..., až v neděli.

6. Zadání

Kombinatorika
Vypočítejte, kolik existuje šesticiferných čísel dělitelných čtyřmi, přičemž každé z nich má právě jednu lichou cifru.

Teorie grafů
Na večírku je alespoň 6 osob. Někteří se znají a někteří ne. POZOR! Zde chápeme relaci "býti známý s" jako symetrickou relaci, tedy zná-li se x s y, tak y se zná s x. Dokažte, že mezi těmito lidmi je určitě nějaká trojice lidí, kteří se všichni navzájem znají, nebo trojice lidí, kteří se všichni navzájem neznají.
Návod: Představte si kompletní graf K_n, n≥6, jehož vrcholová množina představuje jednotlivé lidi na večírku a má dva druhy hran. Jedny symbolizují, že se koncové vrcholy znají, druhé, že se koncové vrcholy neznají.

7. Zadání

Kombinatorika
Dokažte, že pro všechna přirozená čísla n>10 je 2ⁿ větší než n³.

Teorie grafů
Ve výpočetním clusteru je zapojeno 2m+1 počítačů, každý je propojen kabelem s alespoň m dalšími počítači. Ukažte, že celá síť je jistě souvislá. Platí tvrzení i pro cluster s 2m+2 počítači? Své rozhodnutí dokažte.

8. Zadání

Kombinatorika
Mějme permutaci π. Nechť π(i) je obraz prvku i∈{1, 2, ..., n} v permutaci π a nechť j∈{1, 2, ..., n}, i<j. Potom inverzí v permutaci π = (π(1), π(2), ...,π(n)) rozumíme dvojici i,j, pokud π(i) > π(j). Je zřejmé, že identita ι, což je permutace (1, 2, ..., n), nemá žádnou inverzi. Kolik inverzí má permutace, která vznikne z identity ι záměnou právě dvou čísel a,b∈{1, 2, ..., n}, kde a<b, t.j. permutace (1, 2, ..., a-1, b, a+1, ..., b-1, a, b+1, ..., n)?

Teorie grafů
Dokažte, že acyklický graf s n vrcholy a m hranami je nesouvislý právě tehdy, když 1<n-m. Jak zjistíme počet komponent acyklického nesouvislého grafu, když známe pouze počet vrcholů a hran tohoto grafu?

9. Zadání

Kombinatorika
Kolika různými způsoby lze na šachovnici rozestavit
(a) 8 věží tak, aby se žádné dvě neohrožovaly?
(b) k věží, 1≤k≤8, tak, aby se žádné dvě neohrožovaly?
(c) zobecněte vzorec pro k věží a šachovnici o rozměrech n×m.

Teorie grafů
Nechť V(G) grafu G je množina všech dvouprvkových podmnožin množiny [1,5] a nechť jsou vrcholy x,y sousední právě tehdy, když x a y jsou množiny disjunktní. Jakou délku má nejkratší cyklus v tomto grafu? Své tvrzení dokažte!

10. Zadání

Kombinatorika
Obyvatelé staroegyptské říše zapisovali zlomky jako součet převrácených hodnot různých celých čísel, například 4/5 = 1/2 + 1/4 + 1/20. Nalezněte algoritmus, který převede libovolný zlomek p/q, 1<p<q do tohoto staroegyptského tvaru.
Návod: Tento problém lze nalézt v literatuře.

Teorie grafů
Nechť strom T na 2n, n≥2, vrcholech má úplné párování. Dokažte, že T má vrchol stupně 1, který je sousední s vrcholem stupně dva.
Poznámka: Úplné párování v grafu G je množina nezávislých hran (žádné dvě nemají společný koncový vrchol) v grafu G taková, že každý vrchol grafu G je koncovým vrcholem přesně jedné hrany tohoto párování.

Náhradní referát

Kombinatorika
Mějme množinu [1,n] a její permutaci π. Řád permutace je takové nejmenší kladné přirozené číslo k, že platí π^k = π(π(π(...(π)))) = i, kde i je identické zobrazení. Navrhněte algoritmus, který pro dané n najde permutaci nejvyššího řádu. Potom nalezněte příklad takové permutace pro n = 10, 12, 20.

Teorie grafů
Vesmírná stanice má tvar prstence (anuloidu). Na povrchu válce je umístěno šest antén a každá je spojena kabelem, který vede po povrchu válce se všemi pěti ostatními anténami. Kabely se nikde nekříží. Zakreslete možné umístění antén a položení kabelů a nebo dokažte, že takové zapojení není možné.

Mnoho zdaru při řešení samostatného referátu!

Poznámka

Pokud najdete v textu zadání chybu, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit.