MB104, příklady k domácímu rozjímání jarní semestr 2015, devátý týden
Příklad 1. Mějme balíček 32 (různých) karet, 8 karet od každé ze čtyř barev. Kolik existuje rozdání těchto karet čtyřem hráčům (každému osm karet) takových, že každý hráč má dvoubarevný list (tj. mezi jeho osmi kartami jsou karty pouze dvou barev)? (jednobarevný list není dvoubarevný)
Řešení. Očíslujeme-li barvy i hráče od jedné do čtyř, tak přiřazení barev hráčům je čtyřprvková permutace. Rozdání rozdělíme na dva disjunktní případy:
• O dvě barvy se dělí dva hráči, tedy zmíněná permutace je složením dvou transpozic. Takových rozdání je
Permutace je cyklus délky čtyři. Takových rozdání je
Celkový počet uvažovaných rozdání je součtem těchto dvou případů.
□
Příklad 2. Uvažme tabulku n x m, n > 2, m > 2. Každé její políčko je obarveno jednou ze čtyř barev (bíle, zeleně, červeně, či modře) tak, že v libovolném čtverci 2 x 2 se vyskytují políčka všech čtyř barev. Kolik je takových obarvení?
Řešení. Snadno se ukáže, že tabulka musí mít dvoubarevné řádky nebo dvoubarevné sloupce (předpokládáme tři různé barvy vedle sebe v řádku a přístupem „sudoku" dojdeme k tomu, že musejí být dvoubarevné sloupce). Celkem máme (^(Z"1 — 2") — 4! obarvení. □
1