Samostatná práce pro první dva listopadové týdny
(princip inkluza a exkluze, kompozice a rozklady)
Úlohy vypracujte na zvláštní papír a vypracované odevzdejte na přednášce 16. listopadu 2011.
Cvičení 0.1 Kolik anagramů z písmen slova TIKTAK takových, že v nich žádná dvě stejná písmena nestojí vedle sebe, lze vytvořit?
[84]
Cvičení 0.2 V oddělení pracuje několik osob, z nichž každá zná alespoň jeden z těchto jazyků: ruština, španělština, italština. Rusky mluví 6 osob, španělsky 6 osob, italsky 7 osob, rusky a španělsky mluví 4 osoby, španělsky a italsky 3 osoby, rusky a italsky 2 osoby, všechny tři uvedené jazyky ovládá 1 osoba. Kolik osob pracuje v oddělení? Kolik znich mluví pouze rusky? Kolik z nich mluví pouze francouzsky?
[11; 1; 3]
Cvičení 0.3 Na třídní schůzce informoval učitel rodiče takto: "Naše třída má 30 žáků. Mohou chodit do 4 zájmových kroužků, z nichž každý probíhá jednou týdně. Pondělní kroužek navštěvuje 19 žáků, úterní 13, středeční 18 a čtvrteční 11. Žádný žák nenavštěvuje více než dva kroužky a žádné dva kroužky nemají více než 5 společných žáků." Určete, zda učitel mluvil pravdu.
[Ne. Návod: použijte princip inkluze a exkluze a selský rozum.]
Cvičení 0.4 Kolika způsoby lze na šachovnici n x n rozestavit n věží tak, aby každé neobsazené pole šachovnice bylo ohrožováno nějakou věží?
[2nn — n\ Návod: zkuste pro šachovnice o rozměrech 2x2,3x3, atd.]
Cvičení 0.5 Máme pět obálek s adresami (pro 5 různých lidí) a pět dopisů. Kolika způsoby můžeme vložit dopisy do obálek tak, aby ani jeden dopis nebyl ve správné obálce?
[120]
Cvičení 0.6 Vypište všechny kompozice čísla 10 ze čtyř sčítanců.
Cvičení 0.7 Vypište všechny kompozice čísla 10 z nejvýše 4 sčítanců.
Cvičení 0.8 Vypište všechny rozklady čísla 12 na 5 sčítanců.
Cvičení 0.9 Vypište všechny rozklady čísla 12 na 3 sčítance takové, že každý ze sčítanců je roven nejvýše 6.
Cvičení 0.10 Vypočtěte počty kompozic a rozkladů uvedených v přechozích příkladech pomocí vzorce pro výpočet počtu kompozic a rekurentního vzorce pro výpočet počtu rozkladů.
[Vzorce viz skriptum Eduard Fuchs, Diskrétní matematika pro učitele, PřF MU Brno, 2001, str. 48 a 50.]