Sbírka matematických úloh

Taneční pořádek

Úloha číslo: 4513

• Řešení

  Úlohu můžeme zúžit na rozmístění 11 tanců, protože pro country nemáme jinou než poslední 12. pozici

  Nejprve si uvědomíme, že pokud každá vybraná pozice pro rychlé a pro pomalé tance odpovídá \(3!8!\) možnostem, jak do těchto pozic rozmístit rychlé, resp. pomalé tance.

  Při řešení odlišíme čtyři případy podle počtu rychlých tanců v prvním a ve druhém bloku:

  Pokud jsou v prvním bloku tři rychlé tance, musejí být na 2., 4. a 6. pozici, všechny ostatní tance jsou pomalé, čili jde o jednu volbu pozic rychlých tanců.

  Rozbor si zjednodušíme, pokud si uvědomíme následující fakt: Je-li v nějakém bloku \(r\) rychlých a \(p\) pomalých tanců, tak za každým pomalým tancem je potenciální pozice pro rychlý. Počet možných umístění rychlých je dán výrazem \(\binom{p}{r}\), protože nejprve uspořádáme pomalé a poté vybereme ty, za nimiž bude vždy následovat jeden rychlý tanec.

  Pro dva rychlé tance v prvním bloku a jeden ve druhém dostáváme \(\binom{4}{2}\binom{4}{1}\) možností. Pro umístění jednoho rychlého v prvním bloku a dva ve druhém je \(\binom{5}{1}\binom{3}{2}\) možností. Není možné mít tři rychlé tance ve druhém bloku, protože by pak byly dva rychlé za sebou nebo by blok začínal rychlým.

• Odpověď

  Celkový počet možností pro sestavení prvních dvou bloků tanečního pořádku je \(3!8!\left(1+ \binom{4}{2}\binom{4}{1}+\binom{5}{1}\binom{3}{2}\right)=9\,676\,800\).

• Varianta

  Jak by se výpočet změnil, pokud bychom navíc požadovali, aby standardní, i latinskoamerické tance tvořily v rámci bloku souvislé dvojice či trojice? (Mít jich více za sebou v bloku nebo jen jeden by v programu neladilo.)

• Řešení

  Stejně jako v předchozí variantě lze z analýzy vynechat country. Tance rozdělit do pěti skupin: standardní rychlé (2), standardní pomalé (3), latinskoamerický rychlý (1) latinskoamerické pomalé (2) a ostatní pomalé (3). Tance v rámci skupiny jsou zaměnitelné, tedy pokud určíme počet možností, jak pozicím přiřadit skupiny, stačí pak tento počet vynásobit \(2!3!2!3!\) pro výsledný počet možností.

  Latinskoamerické tance tvoří vždy souvislou trojici. Pro ni jsou tři možnosti, kam umístit rychlý jive, ale tato možnost není přípustná, pokud je tato trojice první v bloku.

  Standardní tance vytvoří souvislou dvojici a souvislou trojici. Buď dvojice i trojice obsahují rychlý tanec (to je celkem \(3{\cdot} 2\) možností, pokud nejsou kladeny další podmínky), nebo jen jednu možnost, kdy oba rychlé jsou ve trojici.

  Rozbor případů povedeme podle rozmístění standardních a latinsko-amerických tanců do bloků:

  • Všechny standardní tance jsou v prvním bloku. Potom dvojice a trojice je oddělena ostatním tancem.

    Začne-li blok trojicí, je v ní jeden rychlý tanec a ten nesmí být první. Ve dvojici je jeden rychlý tanec, ale ten může být dříve i později. Pro první blok jde o \(2{\cdot} 2\) možností.

    Začne-li blok dvojicí, pak v ní buď není žádný rychlý tanec a oba se pak vyskytnou v trojici, nebo je ve dvojici rychlý tanec na 2. místě a druhý rychlý může být ve trojici umístěn kdekoli. To je celkem \(1+3\) možností.

    Pokud druhý blok začne trojicí latinskoamerických tanců, jsou dvě možnosti, kam v této trojici umístit rychlý jive. Jinak druhý blok začne pomalým ostatním tancem, a potom lze trojici latinskoamerických tanců umístit na 2.-4. nebo 3.-5. pozici a v této trojici jsou vždy tři možnosti pro rychlý jive. Pro rozmístění tanců ve druhém bloku máme \(2+2{\cdot} 3\) možností.

    Celkem jde o \((2{\cdot} 2 + 1+3)(2+2{\cdot} 3)=64\) možností.

  • První blok začíná trojicí standardních tanců a po něm následuje trojice latinsko-amerických.

    Trojice standardních nutně obsahuje jen jeden rychlý, což dává 2 možnosti. Pro umístění rychlého v trojici latinskoamerických máme 3 možnosti, ovšem jednu možnost třeba odečíst a to tu, kdy by po sobě následovaly rychlý standardní a rychlý latinskoamerický tanec.

    Ve druhém bloku je dvojice standardních. Je-li na začátku, nesmí začínat rychlým, což dává jen jednu možnost. Pokud na začátku není, lze tuto dvojici umístit třemi způsoby a pro každý jsou dvě možnosti, kde bude rychlý tanec.

    Celkem jde o \((2{\cdot} 3-1)(1+3{\cdot} 2)=35\) možností.

  • Pokud první blok začíná trojicí latinsko-amerických následouvanou trojicí standardních, tak je jive na 2. pozici nebo na 3. pozici a obě možnosti mají vliv na rozmístění rychlých standardních tanců:

    • Je-li jive druhý, pak v trojici standardních mohou být dva rychlé (1 možnost) nebo jen jeden (3 možnosti).

      Ve druhém bloku je pak buď dvojice pomalých standardních a tu lze umístit čtyřmi způsoby. Nebo je v této dvojici jeden rychlý. Pokud je tato dvojice první ve druhém bloku, nesmí začínat rychlým, ale pokud je umístěna později, což lze provést třemi způsoby, může být rychlý tanec ve dvojici jak dříve, tak později.

      Celkem jde o \(1 {\cdot} 4 + 3(1+3{\cdot} 2)=25\) možností.

    • Je-li jive třetí, pak ve trojici standardních může být jen jeden rychlý a to na druhém nebo třetím místě.

      Ve druhém bloku je dvojice standardních tanců s jedním rychlým. Pokud je tato dvojice první ve druhém bloku, nesmí začínat rychlým, ale pokud je umístěna později, což lze provést třemi způsoby, může být rychlý tanec ve dvojici jak dříve, tak později.

      Celkem jde o \(2(1+3{\cdot} 2)=14\) možností.

  • První blok se také může skládat z trojice standardních tanců a ze tří ostatních. Pak buď začíná pomalým standardním, což jsou dvě možnosti, nebo některým z ostatních tanců, což dává \(3{\cdot} 3\) možností kdy v trojici standardních je jeden rychlý a 3 možnosti, kdy jsou v trojici oba rychlé.

    Ve druhém bloku je pak dvojice standardních a trojice latinsko-amerických. Podobně jako výše je třeba odlišit, jestli v prvním bloku jsou oba rychlé standardní nebo jen jeden.

    • Když je v prvním bloku jeden rychlý standardní, tak pokud druhý blok pokračuje standardními, musí začínat pomalým a stejně tak i následující trojice latinskoamerických, což jsou jen dvě možnosti. Když druhý blok začíná latinskoamerickými a jive je na 2. pozici, jsou pro následující dvojici standardních dvě možnosti. Naopak, je-li jive třetí, následující dvojice standardních už musí začínat pomalým tancem, což je jen jedna možnost.
    • Jsou-li v prvním bloku oba rychlé standardní, pak druhý blok může začínat standardními a v následující trojici latinskoamerických lze jive umístit kamkoli, nebo druhý blok začíná trojicí latinskoamerických s jive na 2. nebo 3. pozici.

    Celkový počet možností v tomto případě je \((2 + 3{\cdot}3)(2 + 2 + 1) + 3(3+2)= 70\).

  • Pokud první blok obsahuje dvojici standardních s jedním rychlým, trojici latinsko-amerických a jeden ostatní tanec, tak je třeba odlišit tři situce, podle toho, ze které skupiny je první pomalý tanec.

    Je-li standardní, pak druhý je rychlý. Po něm pak následuje ostatní tanec a za ní trojice latinsko-amerických, kde trojici lze uspořádat třemi způsoby. Nebo nejprve trojice latinsko-amerických, v níž první nesmí být rychlý jive, a pak teprve ostatní tanec.

    Je-li latinsko-americký, pak jive je druhý nebo třetí; po něm následuje ostatní tanec nebo dvojice standardních a tuto dvojici lze uspořádat jedním nebo dvěma způsoby, tak, aby rychlý nebyl hned za jive.

    Podobně pokud blok začíná ostatním tancem.

    Ve druhém bloku je pak trojice standardních s jedním rychlým a dva ostatní.

    Tento případ vede na \((3+2 + 2{\cdot} 2 + 2 + 1 + 2(2{\cdot} 3-1))(2+2{\cdot}3)=176\) možností.

  • Pokud první blok obsahuje dvojici pomalých standardních, trojici latinsko-amerických a jeden ostatní tanec, tak je třeba odlišit jestli trojice latinsko-amerických tanců s jediným rychlým jive je první v bloku nebo ne.

    Pokud blok začíná trojicí latinsko-amerických, jde o \(2{\cdot}2\) možností a pokud ne, tak \(4{\cdot} 3\).

    Ve druhém bloku je trojice standardních se dvěma rychlými a dva pomalé ostatní, což vede na dvě možnosti rozmístění.

    V tomto případě jde jen o \((2{\cdot}2+4{\cdot} 3)2=32\) možností.

  Ostatní případy už nejsou možné, protože dvojice standardních a tři ostatní tance nenaplní celý první blok, a kdyby všechny standardní byly ve druhém bloku, tak by jich bylo pět za sebou, což není žádoucí.

• Odpověď

  Celkem je \(2!3!2!3!(64+35+25+14+70+176+32)=59\,904\) možností, jak sestavit první dva bloky programu.

• Komentář

  Varianta úlohy ilustruje, jak celkem přirozená dodatečná podmínka může zkomplikovat rozbor případů.

  Bylo by možné využít i princip inkluze a exkluze, ale rozbor by byl nejspíš podobně složitý.