Narozeninový problém

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V teorii pravděpodobnosti je narozeninovým problémem (či narozeninovým paradoxem) myšlena pravděpodobnost, že pro skupinu náhodně vybraných 23 (či více) lidí je více než 50% pravděpodobnost, že nějací dva lidé budou mít narozeniny ve stejný den. Pro 57 a více lidí je ona pravděpodobnost více než 99%, postupně rostoucí až ke 100 % pro 366 lidí (za předpokladu že pracujeme s rokem o 365 dnech).[1] Matematika skrytá za tímto problémem vede k známému kryptografickému útoku zvanému narozeninový útok.

Pochopení problému[editovat | editovat zdroj]

Narozeninový problém se ptá, zdali „nějaký“ z 23 lidí má shodné datum narození jako „nějaký“ jiný, nikoliv nějaký konkrétní. Pokud v seznamu 23 lidí porovnáváme narozeniny první osoby s ostatními, máme 22 možností na úspěch z celkového počtu 365. Když však porovnáváme každého s každým, je těchto možností 253. To proto, že ve skupině 23 lidí je 23*22/2 = 253 dvojic.

Výpočet pravděpodobnosti[editovat | editovat zdroj]

Graf s křivkou přibližné pravděpodobnosti, že alespoň dva lidé sdílejí narozeniny v dané skupině lidí.

Pro výpočet pravděpodobnosti, že v místnosti s n lidmi alespoň dva mají narozeniny ve stejný den, budeme předpokládat rovnoměrné rozdělení narozenin během roku (tj. budeme ignorovat přestupné roky, dvojčata atd.)

Je jednodušší nejprve spočítat pravděpodobnost p(n), že všech n narozenin je rozdílných. Pro n > 365 je tato pravděpodobnost, s ohledem na Dirichletův princip, rovna nule. Pro n ≤ 365 je dána vzorcem:

Protože druhá osoba nemůže mít stejné narozeniny jako první (364/365), třetí nemůže mít stejné narozeniny jako první dvě (363/365), atd.

Skutečnost, že nejméně dva z „n“ lidí mají stejné narozeniny je komplementární jevu, že všechna data narozenin jsou různá. Proto pravděpodobnost p(n) je

Tato pravděpodobnost překračuje 1/2 pro „n“ = 23 (hodnota kolem 50,7 %). Následující tabulka ukazuje pravděpodobnosti pro některé další hodnoty „n“ (Tabulka ignoruje přestupné roky, jak již bylo výše popsáno):

Tento problém může být vypočítán také jako (1 - variace(365, počet studentů) / variace s opakováním (365, počet studentů)).

n p(n)
10 12%
20 41%
23 50,7%
30 70%
50 97%
100 99,99996%
200 99,9999999999999999999999999998%
300 (100 − (6×10−80))%
350 (100 − (3×10−129))%
366 100%

Poznámky[editovat | editovat zdroj]

  1. Ve skutečnosti však nejsou data narození rozprostřena rovnoměrně v průběhu roku, a to nikoliv pouze kvůli 29. únoru, který se vyskytuje pouze jednou za čtyři roky.[zdroj?]