Počty párování
Úloha číslo: 4589
V první sérii reality show Are you the one? vysílané v roce 2014 na MTV byla skupina 10 žen a 10 mužů tajně spárována do optimálních dvojic. Tito soutěžící měli za cíl toto optimální párování odhalit a v případě úpěchu jim byla slíbena odměna \(1\,000\,000\) USD.
Kolik párování je možné vytvořit (z nichž jen jedno bylo to „správné“)?
Řešení
Každé párování odpovídá prostému zobrazení z desetiprvkové množiny žen do desetiprvkové množiny mužů.
Uspořádejme ženy libovolně do řady. Potom první má na výběr z 10 mužů, druhá už jen z 9, třetí z 8, atd.
Každý takto provedený výběr odpovídá jednoznačně jednomu zobrazení, resp. jednomu párování. Párování je proto \(10!=3\,628\,800\).
Varianta
V osmé sérii vysílané v roce 2019 bylo jen 16 soutěžících, ale nezáleželo na pohlaví, tedy optimální dvojici mohli tvořit i dva muži nebo dvě ženy.
Je za těchto podmínek možných párování více nebo méně než v první sérii?
Řešení
Pokud seřadíme spárované dvojice za sebou, dostaneme uspořádání všech 16 osob, nazvěme je pořadí. Různá párování nutně odpovídají různým pořadím.
Jedno párování však odpovídá více pořadím, protože každá dvojice může být uspořádána dvěma způsoby, a také 8 dvojic může být seřazeno v různém pořadí. Jedno párování odpovídá proto \(2^8 8!\) pořadím.
Všech pořadí je \(16!\). Každé pořadí jednoznačně odpovídá nějakému párování. Proto je počet různých párování roven \(\frac{16!}{2^8 8!}=2\,027\,025\).
Párování je ve skutečnosti méně než v první sérii (s více soutěžícími a s omezením na pohlaví).
