Paradoks dni urodzin
Paradoks dni urodzin[1], paradoks urodzin[2] – paradoks związany z rozwiązaniem poniższego zadania z rachunku prawdopodobieństwa[1]:
- Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej dwóch osób obchodzących urodziny tego samego dnia było równe co najmniej 1/2?
Zakłada się zwykle, że dni urodzin to liczby wybrane z rozkładem jednostajnym ze zbioru co nie odbiega znacząco od rzeczywistości. W szczególności w rozwiązaniu problemu nie uwzględnia się lat przestępnych[1].
Według Iana Stewarta, kiedy grupa badaczy zadała to pytanie studentom, mediana udzielonych odpowiedzi wyniosła 385[3]. Tymczasem już przy 366 osobach zasada szufladkowa Dirichleta gwarantuje, że pewne dwie z nich urodziły się tego samego dnia w roku. Poprawną odpowiedzią jest jednak zaskakująco niewielka liczba 23 osób[1][3], co uzasadnia użycie terminu „paradoks”[1].
Autorstwo problemu przypisuje się Haroldowi Davenportowi[4], który miał wymyślić go około 1927 roku[5]. Davenport wyrzeka się jednak autorstwa[4].
Rozwiązanie problemu
Prawdopodobieństwo zdarzenia przeciwnego do rozpatrywanego, czyli tego, że każda z osób ma inny dzień urodzin, jest przy osobach równe Szablon:Wzór Rozwiązanie problemu równoważne jest ze znalezieniem najmniejszego takiego że Ponieważ ciąg jest nierosnący (co nietrudno zauważyć), wystarczy bezpośrednio obliczyć przy pomocy komputera, że Szablon:Wzór by dojść do prawidłowej odpowiedzi[1].
Aby wykazać, że wystarczą 23 osoby (choć już bez dowodu, że jest to najmniejsza taka liczba), można posłużyć się pewnymi przybliżeniami. Dla każdej liczby rzeczywistej prawdziwa jest nierówność Szablon:Wzór przy czym jest podstawą logarytmu naturalnego. Zatem Szablon:Wzór Aby prawa strona powyższej nierówności była nie większa od musi zachodzić Szablon:Wzór Najmniejszym dodatnim rozwiązaniem tej nierówności jest Szablon:Wzór co jest oczywiście mniejsze od 23[1].
Uogólnienia i powiązane problemy
Inna liczba dni w roku
Przy założeniu, że rok ma dni, rozwiązanie problemu dni urodzin równe jest w przybliżeniu[1] Szablon:Wzór Dla przykładu można rozważyć wspomniany problem dla osób urodzonych na innych planetach Układu Słonecznego[1]:
| Nazwa planety | Czas obiegu wokół Słońca (zaokrąglony) | Minimalna liczność grupy osób |
|---|---|---|
| Merkury | 88 dni | 12 |
| Wenus | 225 dni | 18 |
| Ziemia | 365 dni | 23 |
| Mars | 687 dni | 32 |
| Jowisz | 4 333 dni | 78 |
| Saturn | 10 756 dni | 123 |
| Uran | 30 708 dni | 207 |
| Neptun | 60 223 dni | 290 |
Ustalony dzień urodzin
Problem dni urodzin można zmodyfikować, przyjmując, że przed wykonaniem doświadczenia została wybrana pewna data. Dla ustalenia uwagi, niech będzie to data urodzin przeprowadzającego eksperyment. Należy wówczas znaleźć odpowiedź na pytanie[1]:
- Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej osoby urodzonej tego samego dnia co eksperymentator było równe co najmniej 1/2?
Okazuje się, że potrzeba aż 253 osób. Przy ogólniejszym założeniu, że w roku jest dni, odpowiedź na powyższe pytanie jest równa w przybliżeniu[1] Szablon:Wzór
Związek z kryptografią
Szablon:Zobacz teżSzablon:Dopracować Paradoks dni urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego. Niech dana będzie funkcja skrótu która zwraca kod o bitach, czyli daje możliwych odpowiedzi (jest to moc jej przeciwdziedziny). Jej jakość można ocenić, badając jej jądro, a więc jej kolizje (kolizję tworzą każde dwie znane wiadomości i o których wiadomo, że ).
Każdy kwantyl rozkładu liczby prób potrzebnych do znalezienia kolizji wśród kodów, spełnia zależność Szablon:LinkWzór, gdzie to rząd kwantyla. Średni czas łamania funkcji skrótu (tj. znalezienia kolizji) rośnie więc w przybliżeniu proporcjonalnie do pierwiastka liczby wszystkich możliwych odpowiedzi tej funkcji.
Przypisy
Linki zewnętrzne
- Szablon:Otwarty dostęp Tajemnica dnia urodzin, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 10 października 2017 [dostęp 2024-09-04].