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
. |
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
, |
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ść
, |
przy czym jest podstawą logarytmu naturalnego. Zatem
. |
Aby prawa strona powyższej nierówności była nie większa od musi zachodzić
. |
Najmniejszym dodatnim rozwiązaniem tej nierówności jest
, |
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]
. |
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]
. |
Związek z kryptografią
- Zobacz też: Atak urodzinowy.
Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.
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ść (5), 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
- ↑ a b c d e f g h i j k TomaszT. Nikodem TomaszT., Paradoks dni urodzin i pokrewne, czyli o pewnych zagadnieniach związanych z rozmieszczeniem kul w komórkach, „Delta” (4), Uniwersytet Warszawski, 2010, s. 1-2, ISSN 0137-3005 [dostęp 2024-05-02] (pol.).
- ↑ Matematyka dyskretna: wykłady z przykładami w języku Python, Sułkowice: Wojciech Broniowski, 2021, s. 79, ISBN 978-83-962099-1-7 (pol.).
- ↑ a b IanI. Stewart IanI., What a Coincidence!, „Scientific American”, 278 (6), 1998, s. 95–96, DOI: 10.1038/scientificamerican0698-95, ISSN 0036-8733 [dostęp 2024-05-02] (ang.).
- ↑ a b Isidore JacobI.J. Good Isidore JacobI.J., Probability and the weighing of evidence, Londyn: Griffin, 1950, s. 38 [dostęp 2024-05-02] (ang.).
- ↑ DavidD. Singmaster DavidD., Sources in Recreational Mathematics: An Annotated Bibliography [online], Puzzle Museum, 2004, 8.B. BIRTHDAY PROBLEM [dostęp 2024-05-02] (ang.).
Linki zewnętrzne
- 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].
- Britannica: topic/birthday-problem