Redukce řešení

Jak spočítám počet lidí ve třídě? No přece všichni zvednou ruce, spočítám počet prstů a vydělím desíti!

A proč desíti? Protože jeden člověk má deset prstů!

   Redukce: 10 prstů -> 1 člověk

   Mám-li ve třídě 80 prstů vím, že je tam 80/10 = 8 lidí.

 

 

A co když jsem napočítala 60 prstů, ale mám ve třídě ufony a neznám jejich anatomii?

Vezmu jedno konkrétního ufona a spočítám mu prsty. Zjistím-li že má 3 prsty na rukou (na jedné 2 a na druhé 1) a použiju redukci 3 -> 1 a celkový počet prstů vydělím třema. 60/3 = 20 ufonu.

 

 

Záleží na pořadí vs. Nezáleží na pořadí

Kolika způsoby vyberu 5 karet z balíčku 52 karet (různých karet)?

  • Pokud mi záleží na pořadí v kterém karty tahám. Takže {3♠, K♠, 5♦, 8♥, 8♦} a {3♠, 5♦, 8♥, 8♦, K♠} považuji za dva různé způsoby, pak řešením je 52 * 51 * 50 * 49 * 48 = 311 875 200 způsobů.
  • Pokud nezáleží na pořadí ve kterém mi přišly do ruky, protože si je stejně v ruce přeskládám, pak bude určitě řešení určitě menší. Minimáln výše zmíněné dva způsoby se mi zredukují na jeden. Ale asi je jasné, že toto nejsou jediné dva způsoby kterými si mohu v ruce přeskládat tyto konkrétní karty. Musím to tedy zjistit:
    Kolika způsoby lze v ruce přeskládat karty 3♠, 5♦, 8♥, 8♦, K♠? Na první místo vybírám z pěti karet k tomu můžu přidat libovolnou kartu ze zbývajících čtyř na třetí místo už může příjít libovolná kara ze zbylých tří atd. Tedy 5 * 4 * 3 * 2 * 1 = 120 způsobu jak si přeskládat v ruce konkrétní karty.
    A jelikož nám nezáleží na pořadí karet v ruce, všechny tyto způsoby jak je v ruce přeskládat se nám redukují na jedno jediné řešení => Redukce: 120 -> 1 neboli 5 * 4 * 3 * 2 * 1 -> 1.
    Když 120 způsobů (výběru karet) kdy nám záleží na pořadí se redukuje na 1 způsob kdy nám nezáleží na pořadí. Pak celkový počet 311 875 200 způsob kdy záleží na pořadí (výsledek z první části) se zredukuje na kolik způsobu kdy nezáleží na pořadí?
    311 875 200 / 120 = (52 * 51 * 50 * 49 * 48) / (5 * 4 * 3 * 2 * 1)
Kam dál?