První sada zadání

Napsat referát z předmětu Diskrétní matematika musí každý student sám, žádná spolupráce na textu referátu není dovolena. Je však povoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních. Hodnocení referátů je buď 0 nebo 10 bodů, tj. stylem ANO/NE. V případě mimořádně kvalitního referátu lze udělit i 20 bodů. Referát odevzdáváte e-mailem 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í.

Každý referát vypracujete formou odborného článku, tj. musí mít nadpis, jméno, abstrakt a přehledné členění na sekce, to vše psáno na počítači v rozsahu asi 2 až 5 stran A4. Abstrakt je zhruba jeden 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 opište vlastními slovy v úvodu, popište co jste vlastně řešili. Pro ukázku správného stylu uvádíme dva referáty DIM z roku 2003: 1. referát a 2. referát s extra body.

K vybranému tématu se přihlásíte v KatISu (až do nastavených limitů). Následují zadání první sady samostatných referátů pro předmět Diskrétní matematika.

1. Suma

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Vyjádřete jednoduchým vzorcem bez použití sumy následující výraz pro m ≤ n

2. Dělitelnost

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Nechť p je prvočíslo a n, k jsou přirozená čísla.

(a)	Dokažte, že pro 0 < k < p je dělitelné p.
(b)	Dokažte, že je dělitelné p právě když je dělitelné p.

Návod (b): Ukažte, že v čitateli vzorce pro výpočet je jediny činitel dělitelný p a tedy p dělí právě když p² dělí tento činitel.

Upozornění: Nelekejte se! Při pečlivém rozboru je možno získat i 20 bodů.

3. Čokoláda

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Tabulka čokolády se skládá z m × n čtverečků. Chceme ji nalámat na jednotlivé čtverečky. Jaký je nejmenší počet zlomů, kolikrát budeme lámat, abychom ji rozdělili na jednotlivé čtverečky? Při každém lámání dělíme jen jeden díl na dvě části.

Návod: odhadněte obecný vztah a dokažte matematickou indukcí.

4. Poštovní známky

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Uvažujme arch poštovních známek - m × n kusů. Dále mějme aršíky čtyř známek, což znamená, že jde o jediný kus, kde známky nikdy nejsou spojeny rohem. Kolik různých aršíků daného tvaru lze vytvořit z obdélníkového archu, který obsahuje m × n známek?

Návod: Uvažujte všechny možné tvary aršíků, je jich 5.

5. Trojúhelníky

Referát vypracovaný podle pokynů posílejte na adresu: Pavla<tečka>Kabelikova<zavináč>vsb<tečka>cz.

Kolik různých trojúhelníků můžeme sestavit ze stran délek n, n+1, n+2, ..., 3n. Uvažujte také podobnost trojúhelníků a z množiny podobných trojúhelníků vyberte právě jeden.

Návod: Pro jednoduchost uvažujeme neshodné trojúhelníky. Stejnolehlé trojúhelníky jsou podobné ale nejsou shodné.
Pro trojúhelníky, které nejsou shodné, můžeme předpokládat a ≤ b ≤ c. Snadno najdeme počet všech takový trojic z množiny {n, n+1, n+2, ..., 3n}. Je ale nutno odečíst nevyhovující trojice, které nesplňují trojúhelníkovou nerovnost a + b > c.
Všimněte si, že v nevyhovujících trojicích je c = 2n + k, kde k = 0, 1, n. Označíme a=n+i, b=n+j, kde 0 ≤ i ≤ j a současně i+j ≤ k. Ukažte, že ke každé přípustné hodnotě i existuje k+1-2i možností pro j a celkem že přípustných dvojic a, b je pro k liché 1/4(k+1)(k+3) a pro k sudé 1/4(k+2)².
Nakonec sečtěte počty všech nevyhovujích trojic jako sumu pro všechny hodnoty k. S využitím vztahů

6. Lego

Referát vypracovaný podle pokynů posílejte na adresu: Pavla<tečka>Kabelikova<zavináč>vsb<tečka>cz.

Kolika způsoby lze spojit 2 LEGO kostičky - červenou a modrou (záleží na pořadí) o rozměru m × n? (Předpokládáme, že dílky jsou spojeny alespoň dvěma výstupky.)

7. Věže na šachovnici

Referát vypracovaný podle pokynů posílejte na adresu: Tomas<tečka>Kupka<tečka>fei<zavináč>vsb<tečka>cz.

Kolika způsoby lze na šachovnici postavit

(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 pro šachovnici rozměru m × n

Sestavte obecný vzorec pro k věží.

8. Kostky

Referát vypracovaný podle pokynů posílejte na adresu: Tomas<tečka>Kupka<tečka>fei<zavináč>vsb<tečka>cz.

Máme šest šestistěnných kostek. Hodíme jednou kostkou a zapíšeme počet ok n.
Nyní hodíme n-krát (7-n) kostkami (čti 7 mínus n kostkami). Jaká je střední hodnota součtu všech ok, která při těchto n hodech padnou?

Bonus. Pokrytí šachovnice

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Ukažte, že není možné pokrýt šachovnici o rozměru n × n, na které chybí všechna čtyři rohová políčka, dílky tetrisu ve tvaru "T".

Tato úloha je obtížná, její správné a úplné řešení je za 20 bodů.

Mnoho zdaru při řešení samostatných referátů!

Poznámka

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