Paradoxa del natalici

Archiu:Birthday Paradox.svg

El problema del natalici, també cridat paradoxa del natalici, establix que d'un conjunt de 23 persones, hi ha una provabilitat del 50.7 % de que a lo manco dos d'elles complixquen anys el mateix dia. Per a 57 o més persones la provabilitat és major del 99.166 %. En sentit estricte açò no és una paradoxa ya que no és una contradicció llògica; no obstant, és una veritat matemàtica que contradiu l'intuïció comuna. Molta gent pensa que la provabilitat és molt més baixa, i que fan falta moltes més persones per a que s'alcance la provabilitat del 99.166 %.

En teoria de la provabilitat, el problema del natalici planteja la provabilitat de que, en un conjunt de n persones elegides a l'encert, a lo manco dos compartixquen natalici.

La paradoxa del natalici és una paradoxa verídica: a primera vista sembla errònea, pero en realitat és certa. Encara que puga semblar sorprenent que només es necessiten 23 individus per a alcançar una provabilitat del 50 % d'un natalici compartit, este resultat es fa més intuïtiu si es considera que les comparacions de natalicis es faran entre totes les parelles possibles d'individus. En 23 individus, hi ha 23 × 22 / 2 = 253 parells a considerar, molt més de la mitat del número de dies d'un any.

Les aplicacions del problema del natalici en el món real inclouen un atac criptográfico cridat atac del natalici, que utilisa este model provabilístic per a reduir la complexitat de trobar una colisió per a una funció hash, aixina com per a calcular el risc aproximat de que existixca una colisió hash dins dels hashes d'un determinat tamany de població.

El problema s'atribuïx generalment a Harold Davenport entorn a 1927, encara que no ho va publicar en el seu moment. Davenport no va afirmar ser el seu descobridor «perque no podia creure que no s'haguera plantejat abans». La primera publicació d'una versió del problema del natalici va ser de Richard von Mises en 1939.^[1]^[2]

Estimació de la provabilitat

Calcular esta provabilitat és el problema del natalici. La teoria va ser descrita en American Mathematical Monthly en 1938 en la teoria de Estimació del total de població de peixos en un llac de Zoe Emily Schnabel, baixe el nom de captura-recaptura estadística.^[3]

La clau per a entendre la paradoxa del natalici és pensar que hi ha moltes possibles parelles que complixquen anys el mateix dia. Específicament, entre 23 persones, hi ha 23 × 22 / 2 = 253 parells, i cada u és candidat potencial per a complir la paradoxa. Açò no significa que si una persona entrara en una habitació en 22 persones, la provabilitat de que qualsevol complixca anys el mateix dia que qui entra, és del 50 %. És molt més baixa. Açò es deu a que ara solament hi ha 22 parells possibles. El problema real de la paradoxa del natalici consistix en preguntar si el natalici de qualsevol de les 23 persones coincidix en el natalici de alguna de les atres persones.

Calcule's la provabilitat de que, en una habitació en n persones, a lo manco dos complixquen anys el mateix dia, rebujant els anys bisiestos i les persones bessones, i assumint que existixen 365 natalicis que tenen la mateixa provabilitat. Un método és calcular primer la provabilitat de que cap persona complixca anys el mateix dia que una atra, la qual ve donada per

p = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \dots \frac{365 - n + 1}{365}

perque la segona persona no pot tindre el mateix natalici que el primer (364 / 365), la tercera persona no pot tindre el mateix natalici que les dos primeres (363 / 365), etc. Usant notació factorial, pot ser escrita com

p = {\begin{matrix} \frac{365!}{36 5^{n} (365 - n)!}, & 1 \leq n \leq 365 \\ 0, & n > 365 \end{matrix}

Ara, 1 - p és la provabilitat de que a lo manco dos persones tinguen el mateix dia de natalici. Per a n = 23 s'obté una provabilitat d'al voltant de 0,507.

1 - p = {\begin{matrix} 1 - \frac{365!}{36 5^{n} (365 - n)!}, & 1 \leq n \leq 365 \\ 1, & n > 365 \end{matrix}

En contrast, la provabilitat de que qualsevol en una habitació de n persones (exclós Ud.) tinguen el mateix dia de natalici que vosté està donada per

1 - {(\frac{364}{365})}^{n}

que per a n = 22 solament dona al voltant de 0.059, i es necessitaria a lo manco una n de 253 per a donar un valor superior a 0.5.

La solució es pot generalisar per a incloure als naixcuts un 29 de febrer, naturalment d'un any bisiesto. És una solució, pot haver unes atres, la ventaja d'esta és que és exacta i senzilla. S'usa l'algoritme que figura més arriba (en 365, hi haja persones naixcudes en anys bisiestos o no) en els següents canvis:

Sean nb les persones presents que complixen anys el 29 de febrer.

Si nb = 0; Aplicar Algoritme. FIN

Si nb = 1; n = n-1; Aplicar Algoritme. FIN

Si nb > 1; hi ha a lo manco 2 persones en la mateixa data de natalici. FIN

Programes informàtics

Els següents programes calculen les provabilitats des d'1 fins a 100:

C

#include <stdio.h>
#include <stdlib.h>
 
#definix MAX_VALUE 100000

int calculate(int people_n) {

   double n = 1;
   
   for(int i = 0 ; i < people_n ; i++)
      n = n * (365 - i) / 365;
      
   n = 100 * (1 - n);
   
   return n;
   
}
 
int main(int Arc, char arc[]) {

    int group_n;
    int percentage;
    
    if(argc < 2) {
    
        printf("Usage: %s <people>
", argv[0]);
        return 0;
        
    }

    group_n = nugue(Argo[1]);
    
    if(group_n < 0 || group_n > MAX_VALUE)
        return 1;
        
    percentage = calculate(group_n);

    printf("La provabilitat de que en un grup de %d persones, dos complixquen anys el mateix dia és d'un %d%%.
", group_n, percentage);
    
    return 0;
    
}

C++

#include <iostream>
 
using namespace std;
 
long double calcular(int persones)
{
   long double p=1;
   for(int i=0;i<persones;i++)
   {
      p=p*(365-i)/365;
   }
   p=100*(1-p);
   return p;
}
 
int main() 
{
  int grup;
  long double provabilitat;
  cout << "Introduïx quantes persones té el grup : ";
  cin >> grup;
  provabilitat = calcular(grup);
  cout << "La provabilitat de que en un grup de " << grup << " persones, dos complixquen anys el mateix dia és d'un " << provabilitat
  << "%" << endl;
  return 0;
}

C#

El següent programa calcula les provabilitats depenent del número de persones (grup):

        static void Main(string[] args)
        {
            Console.WriteLine("Introduïx el número de persones: ");
            int num = Convert.ToInt32(Console.ReadLine());
            Complix(num);
            Console.Read();
        }
        static void Complix(int num)
        {
            double p = 1.0;
            for (int i = 1; i <= num; i++)
            {
                p = p * (366 - i) / 365; //Formula de natalici
            }
            Console.WriteLine(100*(1 - p));
        }

Javascript

let p = 1.0

for (let i = 1; i <= 100; i++) {
    p = p * (366 - i) / 365
    console.log('&#36;{i}: &#36;{1 - p}')
}

Ruby

pr = 1.0
1.upto(100) do |i|
  pr = pr * (366 - i) / 365
  puts "#{i}: #{1 - pr}"
end

Go

package main

import "fmt"

func main() {
  p := 1.0
  for i := 1; i <= 100; i++ {
    p = p * (366 - float64(i)) / 365
    fmt.Println(i, ":", 1 - p)
  }
}

Rust

fn main() {
    provabilitat_dos_persones_complixen_mateix_dia(100);
}

fn provabilitat_dos_persones_complixen_mateix_dia(numere_persones: o32) {
    let mut provabilitat = 1.0;

    for i in 1..(numere_persones + 1) {
        let i = i as f32;

provabilitat = provabilitat * (366.0 - i) / 365.0;
        let procentaje = 100.0 * (1.0 - provabilitat);
        println!("Per a un grup de {} persones, la provabilitat de que dos persones complixquen anys el mateix dia és de el {}%",
        i, procentaje);
    }
}

Julia

println("Número de persones : Provabilitat")
p = 1
for i in 1:100
    p = p * (366 - i) / 365
    printf("%d : %10.6f
",i,1-p)
end

Pascal

Program Complixes ;
Var
   i : Integer ;
   p : Real ;
Begin
   writeln(' Num  -  Provabilitat') ;
   p := 1.0 ;
   For i := 1 to 100 Do
   Begin
      p := p * (366 - i) / 365 ;
      write(i:3,100*(1-p):17:6) ;
      readln ;
   End ;
End.

Python

print('Num. provabilitat')
p = 1
for i in range(1, 80):
    p = p * (366 - i) / 365
    print(f'{i}: {(1-p):.3f}')

Perl

print ('Num. provabilitat');
my &#36;p = 1.0;
foreach( 1..100 ) {
        &#36;p = &#36;p * (366 - &#36;_) / 365;
        print &#36;_, ' : ', 1-&#36;p, "
";
}

Java

El següent programa calcula les provabilitats depenent del número de persones (grup):

import java.util.Scanner;

public class ProblemaDelCumpleanos {
    public static void main(String[] args) {
        Scanner entrada = new Scanner(System.in);
        System.out.println("Introduïx el número de persones: ");
        int tamanoDePoblacion = (entrada.nextInt());
        System.out.println(complix(tamanoDePoblacion));
        entrada.next();
    }

    /**
     * param num Tamany de la poblacion usada per a calcular la provabilitat.
     * return Provabilitat entre la poblacion hi haja 2 persones que tinguen el
     * mateix natalici.
     */

    public static double complix(int num) {
        double provabilitat = 1.0;

        for (int i = 1; i <= num; i++) {
            provabilitat = provabilitat * (366 - i) / 365;
        }

        return (100 * ((1 - provabilitat)));
    }
}

PHP

function paradoxa(&#36;grup){
  &#36;p = 1.0;			
  for (&#36;i = 1; &#36;i < &#36;grup; &#36;i++){
    &#36;p = &#36;p * (366-&#36;i) / 365;		
  }	
  &#36;p = 1.0 - (1.0 * &#36;p * (366-&#36;i) / 365);
  return &#36;p;
}  
tire paradoxa(NUMERO);

PL/SQL

El següent programa té en conte els anys bisiestos (és dir, es requerixen 367 persones per a garantisar una provabilitat del 100 %).

Calcula totes les provabilitats des de n = 1 fins a n = 367 persones.

Note's que pel llímit de decimals que PL/SQL pot manejar, si el número de persones és superior a n=227 (provabilitat 99.99999999999999999999999999999999999999 %), llavors PL/SQL redoneja la provabilitat al 100 %.

SET SERVEROUTPUT ON

DECLARE
  P REAL := 1;
  I INTEGER;

BEGIN
  FOR I IN 1..367
  LOOP
        P := P * (367-I) / 366;    
        DBMS_OUTPUT.PUT_LINE ('Per a n=' || I || ': Provabilitat ' || 100*(1-P) || '%');    
  END LOOP;
END;

MATLAB

%Script_Complix_v3
%inclou bisiestos
clc,clear,close all,format compact,format short
disp('Num : Provabilitat')
prob=1;
for loop=1:367
    prob=prob*(367-loop)/366;
    fprintf('%3.0f : %6.4f 
', loop, 1-prob)
    if (1-prob<0.99)
      plot(loop,1-prob,'*');
      hold on
    
end end
hold off
grid on
title('Provabilitat que en un grup, dos persones el mateix dia complixquen anys')
xlabel('Número de persones en el grup')
ylabel('Provabilitat')

Microsoft SQL Server

La següent consulta calcula les provabilitats depenent del número d'Persones

DECLARE Persones INT

SET Persones = 23;

WITH TBL AS (
    SELECT 1 i, cast(1 as real) p
    UNION ALL

SELECT i+1, cast((365-i)/365.0 as real)
    FROM TBL
    WHERE i < Persones
)
SELECT (1-exp(sum(log(p))))*100 Provabilitat
FROM TBL
OPTION (MAXRECURSION 0)

R

total=1; 
for(i in 1:100) { 
  total=total*((366-i)/365)
  cat("La provabilitat de que en un grup de ", i, " persones, a lo manco dos complixquen anys el mateix dia és de: ", 1-total,"
")
}

Scala

object ProblemaDelCumpleanos {

   def complix(n: Int) : Double = {
     (1 to n).foldLeft(1.0)((prob, i) => prob * (366 - i)/365.0)
   }

   def main(args: Array[String]) : Unit = {
      val persones = 25
      println(s"La provabilitat de que en un grup de &#36;persones persones, a lo manco dos d'elles complixquen anys el mateix dia és: &#36;{complix(persones)}")
   }
}

Swift

func complix(grup: Int) -> Double {
    var p:Double = 1
    if grup > 1 {
        for i in 1...grup {
            p = p * Double(366-i)/365.0
        }
    }
    return 1-p
}

let persones: Int = 25
let percentage: Double = complix(grup: persones) * 100

print("La provabilitat de que en un grup de (persones) persones, existixquen dos persones que complixquen el mateix dia és de (percentage)%");

Referències

↑ Internet Archive, Isidore Jacob (1950). Probability and the weighing of evidence, London, C. Griffin.
↑ P. Diaconis, F. Mosteller: Methods for Studying Coincidences. En: Journal of the American Statistical Association. 84, 4, P. 853–861.
↑ Knuth (1997). The Art of Computer Programming, 2. edició, Addison-Wesley, p. 513. ISBN 978-0-201-89685-5.

Referències

Este artícul conté una traducció derivada de «Paradoja del cumpleaños» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Internet Archive, Isidore Jacob (1950). Probability and the weighing of evidence, London, C. Griffin.

[2] P. Diaconis, F. Mosteller: Methods for Studying Coincidences. En: Journal of the American Statistical Association. 84, 4, P. 853–861.

[3] Knuth (1997). The Art of Computer Programming, 2. edició, Addison-Wesley, p. 513. ISBN 978-0-201-89685-5.

[1]

[2]

[3]