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.

Bodování
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í.

Struktura referátu
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.

Termín odevzdání
Termín odevzdání je v pondělí 6.12.2010 ve 12:00. (přednášku ve 12:30 lze stihnout)
Číslo zadání bude studentům přiděleno na cvičení. Můžete se podívat na vzorový referát ve formátu pdf: dim_vzorovy_referat.pdf.

1. Zadání

Kombinatorika
Dokažte, že existuje číslo tvaru 20102010...2010, které je dělitelné 1111.
Návod: Každé číslo tvaru 20102010...2010 lze zapsat jako x_i = 10^4(i-1)n + 10^4(i-2)n + ... +10⁴n + n = n(10^4(i-1) + 10^4(i-2) + ... +10⁴ + 1), pokud n=2010. Součet v závorce se dá pěkně vyjádřit. Pak volte i=1, 2, ..., 1112 a ukažte pomocí Dirichletova principu, že vždy existují x_i, x_j, j>i, taková, že číslo x_j - x_i je dělitelné 1111.

Teorie grafů
Existuje více neizomorfních grafů se stupňovou posloupností (1,1,2,3,4,4,5,5,5,6) nebo grafů se stupňovou posloupností (3,4,4,4,5,5,6,7,8,8)? Pečlivě zdůvodněte!
Návod: Mějme graf G. Potom graf G=(V,E) nazýváme doplněk grafu G právě tehdy, když V = V a E={ xy | x,y ∈ V, xy ∉ E }.

Jestliže se u některých G nadtržítko nezobrazuje správně, tak použijte následující zadání:
Mějme graf G. Potom graf G'=(V',E') nazýváme doplněk grafu G právě tehdy, když V = V' a E'={ xy | x,y ∈ V, xy ∉ E }.

2. Zadání

Kombinatorika
Dokažte, že z 50 libovolně zvolených navzájem různých prvočísel je vždy možné vybrat 13 prvočísel tak, že rozdíl každých dvou z nich je dělitelný 5.

Teorie grafů
V okrsku je 12 obcí a každá s každou je propojena přímým elektrickým vedením. Politická reprezentace regionu chce tuto elektrickou síť pronajmout 6 distributorům el. proudu s tím, že každé přímé vedení bude využíváno nejvýše jedním distributorem a každý distributor bude přivádět proud do všech obcí. Rozhodněte, zda je vůbec možné, něco takového zajistit. Pokud ano, navrhněte rozvodnou síť pro každého distributora tak, aby byly všechny "stejnotvaré".
Upřesnění: Pokud si představíme rozvodnou síť jako graf, tak sítě všech distributorů jsou navzájem izomorfní grafy.

3. Zadání

Kombinatorika
Na šachovnici postavíme dvě dámy na dvě různá náhodně vybraná pole.

• a) Jaká je pravděpodobnost, že se dámy budou ohrožovat?
• b) Úlohy zobecníme na šachovnici n × n polí pro n sudé. Jaká je pravděpodobnost, že se dvě dámy budou ohrožovat?
• c)* Úlohy zobecníme na šachovnici n × n polí pro obecné n. Jaká je pravděpodobnost, že se dvě dámy budou ohrožovat?

Teorie grafů
Pozor, toto zadání nahradilo předchozí verzi!
Turnaje ve stolním tenise se účastní n hráčů (n>3), hrají se dvouhry. Předpokládejme, že turnaj ještě neskončil. Někteří hráči spolu ještě nehráli, ale žádní dva hráči spolu nehráli více než jednou. Tu si někdo všiml, že zatím neexistuje žádná taková trojice hráčů A, B, C, že by tito tři hráči měli odehrané všechny zápasy mezi sebou, tj. nehrál se alespoň jeden ze zápasů AB, BC, nebo AC. Ukažte, že zatím jistě nebylo odehráno více než n(n-1)/3 her z celkového počtu n(n-1)/2 her. Své tvrzení pečlivě zdůvodněte!
Návod: Využijte metodu dvojího počítání. Dvěma způsoby spočítejte kolik existuje v kompletním grafu různých trojúhelníků v₁, v₂, v₃, které obsahují hranu xy.

4. Zadání

Kombinatorika
Máme nepoctivou šestistěnnou kostku. Víme, že číslo 6 padá třikrát častěji než číslo 1, číslo 5 padá dvakrát častěji než číslo 2 a číslo 4 padá stejně často jako číslo 3.

• a) Kolik takových kostek existuje? popište, jak vypadají všechny (nerozlišujeme umístění čísel na kostce, jen pravděpodobnosti jednotlivých stran).
• b) Jaká je střední hodnota počtu ok při jednom hodu? (výsledkem není číslo, ale výraz)
• c) Jaká je největší střední hodnota počtu ok při jednom hodu, které lze při vhodné konstrukci kostky dosáhnout?

Teorie grafů
Obchodní cestující má za úkol navštívit všechna města v daném regionu (všechny vrcholy daného grafu) právě jednou a vrátit se zpět.

• a) Kolik existuje cest obchodního cestujícího v kompletním grafu K_n?
• b) Kolik existuje cest obchodního cestujícího v kompletním grafu bez jedné hrany? (Označme takový graf K_n-xy, kde xy je některá pevně zvolená hrana kompletního grafu.)

5. Zadání

Kombinatorika
Určete všechna dvojciferná přirozená n, pro která platí, že n³-n je dělitelné číslem 100.
Poznámka: Využijte kombinatorické úvahy, rozhodně nemáte dosazovat 90 různých hodnot!

Teorie grafů
Na mariášový turnaj přijelo 7 účastníků. Je možné odehrát tento turnaj v 7 kolech u jediného stolu s tím, že bude hrát každý s každým a v daném kole hrají vždy 3 hráči? Pokud ano, navrhněte rozlosování hráčů do jednotlivých kol.

6. Zadání

Kombinatorika
Máme dvě stejné poctivé kostky. Jak rozmístit oka (nelze použít záporný počet ok) na jejich strany, aby střední hodnota součtu ok na obou kostkách byla stejná, jako střední hodnota součinu ok? Kolik existuje řešení? Najděte je všechna.
Poznámky: Dovolíme-li, aby některé strany měly stejný počet ok, pak předpokládáme, že poctivá kostka musí mít pro každou hodnotu stejný počet stran.
Kostky, které se liší jen permutací stěn, nebudeme rozlišovat.

Teorie grafů
Dokažte, že každý 5-pravidelný rovinný graf obsahuje trojúhelník C₃.

7. Zadání

Kombinatorika
Určete počet všech relací R částečného uspořádání na množině A={ ♣, ♦, ♥, ♠ } takových, že prvek ♣ je nesrovnatelný s prvkem ♠, t.j. (♣,♠) ∉ R, (♠,♣) ∉ R.
Návod: Uvědomte si například, že relaci částečné uspořádání lze zakreslit pomocí Hasseova diagramu.

Teorie grafů
K-land je ostrovní země se silniční sítí, která má konečný počet křižovatek a na každé z nich se kříží přesně K cest. (O K je známo pouze to, že je více než sedmnáct.) Ukažte, že můžete vyjít z nějaké křižovatky, projít alespoň K+1 různých cest, alespoň K+1 různých křižovatek (včetně výchozí), a až v posledním kroku se vrátit na výchozí křižovatku.
Poznámka: Mimoúrovňová křížení cest jsou povolena, v těchto případech se nejedná o křižovatky! Každá ze silnic začíná a končí na jiné křižovatce. To znamená, že smyčky nejsou povoleny. Navíc mezi každými dvěma křižovatkami vede nejvýše jedna silnice.

8. Zadání

Kombinatorika
Najděte všechna trojciferná přirozená čísla n, která jsou shodná s posledním trojčíslím čísla n².
Poznámka: Využijte kombinatorické úvahy, rozhodně nemáte dosazovat stovky různých hodnot!
Návod: Co platí pro rozdíl dvou přirozených čísel, která končí stejným trojčíslím?

Teorie grafů
Mějme v rovině nakreslený pravidelný konvexní n-úhelník Q a některé jeho úhlopříčky tak, aby se žádné dvě nekřížily. Sestavíme graf G, jehož vrcholy budou vrcholy n-úhelníka Q a hrany budou strany nebo úhlopříčky Q. Ukažte, že graf G lze dobře obarvit nejvýše třemi barvami.

Náhradní referát

Kombinatorika
Určete, kolik je prvočísel mezi 100 a 200 (včetně). Při výpočtu použijte princip inkluze a exkluze, nikoliv ověřování dělitelnosti hrubou silou.

Teorie grafů
Ukažte, že rovinný graf, ve kterém jsou tři vrcholy stupně 3, jeden vrchol stupně 5 a všechny zbývající vrcholy jsou stupně 4 nebo 6, musí obsahovat trojúhelník C₃.

Mnoho zdaru při řešení samostatného projektu!

Poznámka

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