Strona główna » Algorytmy » Artykuły » Paradoks Urodzinowy
 

Paradoks Urodzinowy

https://mattomatti.com/a0237

Zagadka

Ile osób musi być w pewnym pomieszczeniu, aby szansa znalezienia dwóch osób urodzonych tego samego dnia była większa niż 50%? Przyjmujemy, że rok kalendarzowy ma 365 dni.

Rozwiązanie

Odpowiedź

Potrzeba zaledwie 23 osób w pomieszczeniu, aby szansa znalezienia dwóch osób o tej samej dacie urodzin wyniosła powyżej 50%!

Wyjaśnienie

Jeśli liczba osób w pomieszczeniu jest mniejsza niż 2 to prawdopodobieństwo wynosi 0%, a jeśli powyżej 365 osób to wyniesie ono 100% (366 dni dla lat przestępnych). Dla pozostałych ilości osób prawdopodobieństwo P(U) liczymy poprzez zdarzenie odwrotne do tego, że nikt nie ma urodzin tego samego dnia. Dla dowolnej grupy n osób wybieramy kolejno dla każdej i-tej osoby pozycję. Szansa na wybranie dnia dotychczas nie odnalezionego wynosi pi = (365 - i + 1)/365. Prawdopodobieństwo, że każdy urodził się innego dnia jest iloczynem każdego pi w danej grupie. Na koniec prawdopodobieństwo, że istnieje para dwóch osób urodzonych tego samego dnia liczymy poprzez zdarzenie przeciwne P(U) = 1 - P(U') = 1 - Πi = 1, .., n pi

Przykładowo licząc dla grupy 23 osób iloczyn to P(U') = (365/365)(364/365)(363/365)..(344/365)(343/365) ~ 49.27%, a więc P(U) = 1 - 49.27% = 50.73%.

Poniżej został przedstawiona zależność prawdopodobieństwa P(n) wystąpienia tej samej daty urodzin od grupy n osób.

Jak można zauważyć prawdopodobieństwo rośnie bardzo szybko, ponieważ dla 23 osób mamy już ponad 50% szans, a powyżej 70 osób jest to już prawie 100%! Dopiero na wykresie dla dowolnej grupy osób widać, że linia znajduje się bardzo blisko 100% (choć osiąga ją dopiero wtedy, gdy liczba osób n jest większa, równa liczbie dni w roku).

Niesamowite, prawda? Paradoks urodzinowy jest wykorzystywany w kryptografii podczas analizy funkcji skrótów. W ten sposób bada się podatność funkcji na tzw. atak urodzinowy tj. znalezienie nieznanego hasła za pierwszym razem.

Implementacja

Obliczenia prawdopodobieństwa mogą zająć bardzo dużo czasu, dlatego warto napisać program, który policzy to za nas. Funkcja SzansaUrodziny() przyjmuje jeden argument n dla którego algorytm oblicza szansę, że w grupie n osób dwie osoby mają urodziny tego samego dnia przyjmując, że rok ma 365 dni.

  1. double SzansaUrodziny(int n) {
  2.   if (n < 2) return 0;
  3.   if (n >= 366) return 1;
  4.   double szansa = 1;
  5.   for (int i = 0; i < n; i++) {
  6.     szansa *= ((double)(365 - i)) / (365.0);
  7.   }
  8.   return 1 - szansa;
  9. }

Testowanie funkcji

Komputery przechowują liczby rzeczywiste w postaci przybliżonej, więc wynik może nie być w 100% dokładny dla coraz to większej ilości mnożonych czynników.

  1. int main () {
  2.   int n;
  3.   cout << "Ile osob w pomieszczeniu?\n n = ";
  4.   cin >> n;
  5.   double szansa = SzansaUrodziny(n);
  6.   double procent = floorf(szansa * 10000.0) / 100.0;
  7.   cout << "Szansa wynosi " << procent << " %";
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz funkcję SzansaUrodziny(), która przyjmie dodatkowy parametr d, który określi ile dni ma rok. Dzięki temu będzie możliwe wyznaczenie prawdopodobieństwa dla lat przestępnych, albo zasymulowania paradoksu na innych planetach, gdzie rok jest krótszy, albo dłuższy. Przykładowo szansa, że wśród 23 osób zachodzi zdarzenie dla 365 dni wynosi 50.72%, a dla 366 dni w roku jest nieznacznie niższe, bo 50.63%.