Permutace

Prodloužení cest je přesně tolik, kolik je cest z $B$ do $C$, tedy $6$.

Výsledek části (a) říká, že počet cest z $A$ do $C$ ($42000$) je šestinásobkem počtu cest z $A$ do $B$, těch je tak $7000$.

1. (a) Budeme postupovat metodou postupného výběru. Na první pozici máme 8 možností. Pro každou volbu první pozice máme přesně sedm možností na druhou pozici. Dále šest možností na třetí a tak dále až na předposlední pozici zbudou dvě možnosti a na poslední možnost jediná. Výsledkem je tedy součin čísel od jedné do osmi, což je 40320.

2. (b) Po povinném umístění Argentiny na čtvrtou pozici, umísťujeme zbylých sedm týmů na zbylých sedm pozic. Zcela obdobně jako v části (a) dospějeme k výrazu $7\cdot 6 \cdots 2 \cdot 1 = 5040$.

3. (c) První čtyři pozice tedy obsadí čtyři mimoevropské týmy a zbylé čtyři ty evropské. Navíc každé pořadí čtveřice evropských lze zkombinovat s každým pořadím čtveřice neevropských. Podle mustru z části (a) seřadíme neevropské týmy jedním z $4 \cdot 3 \cdot 2 \cdot 1 = 24$ způsobů a podobně evropské týmy jedním ze 24 způsobů. Možných kombinací je pak $24^2 = 576$.

4. *(d) Nejprve umístíme pouze USA a Austrálii. Na to máme $8 \cdot 7 = 56$ možností. Pro každou z nich nám zbude šest pozic k obsazení. Na první dvě z nich patří Argentina a Brazílie v jednom ze dvou možných pořadí. Na zbylou čtveřici pozic umístíme evropské týmy jednou z $4 \cdot 3 \cdot 2 \cdot 1 = 24$ možností. Odpověď je pak $56 \cdot 2\cdot 24 = 2688$.

Předpokládejme, že v turnaji není žádná trojice týmů, která se porazila dokola. Ukážeme, že pak už nutně lze nalézt hráče, který vyhrál každý svůj zápas.

Vezměme hráče $A$, jehož nikdo nepřekonal v počtu výher, a ukažme, že jej nikdo nemohl porazit. Pokud by přeci jen nějaký hráč $B$ porazil $A$, porazil by pak i všechny ty, které porazil $A$ (značme je $C$), jinak by trojice $C > B > A > C$ tvořila zakázaný trojcyklus. Takový $B$ ale existovat nemůže, protože by měl alespoň o jedno vítězství více než $A$, což nelze.