Kombinatorika

Přeji pěkný večer, Lukáši.

Jestliže všichni pasažéři nastupují v prvním patře, můžeme zřejmě předpokládat, že v něm nikdo vystupovat nebude. Zbývá tedy \(10\) různých pater, v nichž může výtah zastavit. Jelikož je pasažérů \(9\) a všichni dříve či později vystoupí, zastaví výtah v krajních případech pouze jednou (protože všichni vystoupí současně), nebo devětkrát (protože každý vystoupí jindy), případě počet zastavení bude jiné přirozené číslo mezi \(1\) a \(9\).

Úlohu chápu tak, že je nám jedno, kde který konkrétní pasažér vystoupí, zajímají nás pouze to, kde výtah reálně zastavil. Současně předpokládám, že výtah bude zastavovat tak, že se se současnými pasažéry nebude vracet dolů (tj. pokud někdo má vystoupit třeba ve druhém patře a někdo jiný v pátém, zastaví se nejprve ve druhém a až pak v pátém). Každou možnost tedy můžeme reprezentovat množinou čísel těch pater, v nichž výtah zastaví. Např. množina { \(2, 9, 10\)} znamená, že výtah zastavil právě třikrát (a to v patrech \(2, 9, 10\)).

Otázku tedy můžeme změnit následovně: Pokud máme množinu s deseti prvky, kolik existuje jejích podmnožin, jež mají mohutnost \(1 - 9\)? A to už je poměrně snadná otázka.

Můžeme buďto sečíst kombinační čísla

\(\binom{ 10} { 1} + \binom{ 10} { 2} + \dots + \binom{ 10} { 9} \)

nebo si můžeme uvědomit, že potenční množina desetiprvkové množiny má \(2^{ 10} \) prvků, a že tato potenční množina obsahuje pouze jednu prázdnou a jednu desetiprvkovou množinu, které potřebujeme vyloučit.

Odpovědí tedy je \(2^{ 10} - 2\).

Zdravím,

přidám ještě jeden pohled na problém.

Každou cestu můžeme zakódovat jako 10ti bitový řetězec typu 1001010000, kde 1 znamená, že v daném patře výtah zastavil a 0, že ho projel. Takových řetězců je \(2^{ 10} \) (variace s opakováním). A musíš odečíst 2 řetězce - 0000000000 protože by nikdo nevystoupil a 1111111111, protože by vystupovalo 10 lidí, a ti tam nejsou.