Antecedentes

La paradoja del cumpleaños es un problema popular en la teoría de la probabilidad que desafía la intuición matemática (de la mayoría de las personas). La declaración del problema es:

Dadas N personas, ¿cuál es la probabilidad de que al menos dos de ellos tengan el mismo cumpleaños (sin tener en cuenta el año)?

El problema generalmente se simplifica al ignorar por completo los días bisiestos. En este caso, la respuesta para N = 23 es P (23) ≈ 0.5072972 (como un ejemplo común). El artículo vinculado de Wikipedia explica cómo llegar a esta probabilidad. Alternativamente, este video de Numberphile hace un muy buen trabajo.

Sin embargo, para este desafío queremos hacerlo bien y no ignorar los años bisiestos. Esto es un poco más complicado, ya que ahora es necesario agregar el 29 de febrero, pero este cumpleaños en particular es menos probable que todos los demás.

También usaremos las reglas completas del año bisiesto :

Si un año es divisible por 400, es un año bisiesto.
De lo contrario, si un año es divisible por 100, no es un año bisiesto.
De lo contrario, si un año es divisible por 4, es un año bisiesto.
De lo contrario, no es un año bisiesto.

¿Confuso? Significa que los años 1700, 1800, 1900, 2100, 2200, 2300 no son años bisiestos, pero 1600, 2000, 2400 sí lo son (así como cualquier otro año divisible por 4). Este calendario se repite cada 400 años, y asumiremos una distribución uniforme de cumpleaños durante esos 400 años.

El resultado corregido para N = 23 es ahora P (23) ≈ 0.5068761 .

El reto

Dado un número entero 1 ≤ N < 100, determine la probabilidad de que entre las Npersonas al menos dos tengan el mismo cumpleaños considerando las reglas del año bisiesto. El resultado debe ser un número de coma flotante o de punto fijo, con una precisión de al menos 6 decimales. Es aceptable truncar los ceros finales.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y emitiendo el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Su solución debe poder producir resultados para las 99 entradas en cuestión de segundos. Esto es principalmente para descartar los métodos de Monte Carlo con toneladas de muestras, por lo que si está utilizando un algoritmo principalmente rápido y exacto en un lenguaje esotérico excesivamente lento, estoy dispuesto a dar margen a esta regla.

Casos de prueba

Aquí está la tabla completa de resultados:

 1 => 0.000000
 2 => 0.002737
 3 => 0.008195
 4 => 0.016337
 5 => 0.027104
 6 => 0.040416
 7 => 0.056171
 8 => 0.074251
 9 => 0.094518
10 => 0.116818
11 => 0.140987
12 => 0.166844
13 => 0.194203
14 => 0.222869
15 => 0.252642
16 => 0.283319
17 => 0.314698
18 => 0.346578
19 => 0.378764
20 => 0.411063
21 => 0.443296
22 => 0.475287
23 => 0.506876
24 => 0.537913
25 => 0.568260
26 => 0.597796
27 => 0.626412
28 => 0.654014
29 => 0.680524
30 => 0.705877
31 => 0.730022
32 => 0.752924
33 => 0.774560
34 => 0.794917
35 => 0.813998
36 => 0.831812
37 => 0.848381
38 => 0.863732
39 => 0.877901
40 => 0.890932
41 => 0.902870
42 => 0.913767
43 => 0.923678
44 => 0.932658
45 => 0.940766
46 => 0.948060
47 => 0.954598
48 => 0.960437
49 => 0.965634
50 => 0.970242
51 => 0.974313
52 => 0.977898
53 => 0.981043
54 => 0.983792
55 => 0.986187
56 => 0.988266
57 => 0.990064
58 => 0.991614
59 => 0.992945
60 => 0.994084
61 => 0.995055
62 => 0.995880
63 => 0.996579
64 => 0.997169
65 => 0.997665
66 => 0.998080
67 => 0.998427
68 => 0.998715
69 => 0.998954
70 => 0.999152
71 => 0.999314
72 => 0.999447
73 => 0.999556
74 => 0.999645
75 => 0.999717
76 => 0.999775
77 => 0.999822
78 => 0.999859
79 => 0.999889
80 => 0.999913
81 => 0.999932
82 => 0.999947
83 => 0.999959
84 => 0.999968
85 => 0.999976
86 => 0.999981
87 => 0.999986
88 => 0.999989
89 => 0.999992
90 => 0.999994
91 => 0.999995
92 => 0.999996
93 => 0.999997
94 => 0.999998
95 => 0.999999
96 => 0.999999
97 => 0.999999
98 => 0.999999
99 => 1.000000

(Por supuesto, P (99) es solo 1.0 debido al redondeo. La probabilidad no alcanzará exactamente 1.0 hasta P (367) .)

code-golf probability-theory Martin Ender
fuente

77

1. Si va a ser pedante, entonces debe tener en cuenta que los cumpleaños no se distribuyen de manera uniforme durante todo el año. 2. La relevancia precisa de las reglas del año bisiesto depende de los supuestos sobre la longevidad humana. ¿Es la idea amortizar durante el ciclo completo de 400 años?

Peter Taylor

1

@PeterTaylor Sí, suponga una distribución uniforme durante el ciclo completo de 400 años. Nunca dije que el conjunto de N personas estuviera vivo al mismo tiempo. ;)

Martin Ender

6

Pyth, 31 34 bytes

Jt.2425K366-1c.xX0rK-KQ*JQ^+KJQ

Demostración , prueba de arnés

Esto funciona de manera similar a la versión anterior, excepto que en lugar de generar por separado el valor (366 + n * (.2425 - 1)) y multiplicarlo, comienza generando una lista que se extiende de 366 a 365 - n + 2, luego modifica el 366 en su lugar para convertirse en (366 + n * (.2425 - 1)), y luego toma el producto de la lista. Además, se usan las constantes 366 y -.7575 en lugar de 365 y .2425.

Versión antigua:

Pyth, 34 bytes

J.2425K365-1c*+hK*QtJ.xrK-hKQ^+KJQ

Hay dos formas posibles de que no haya un par de personas con el mismo cumpleaños: que todos tengan cumpleaños diferentes, y que nadie tenga un cumpleaños el 29 de febrero, y que alguien tenga un cumpleaños el 29, y todos los demás tengan un cumpleaños diferente cumpleaños en días normales

La probabilidad de que ocurra por primera vez es (365 * 364 * ... 365 - n + 1) / (365.2425 ^ n).

La probabilidad de que ocurra lo segundo es (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425 ^ n)

Estos se pueden escribir juntos como (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365.2425 ^ n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (.2425 - 1) * n) / (365.2425 ^ n).

Esta es la probabilidad de que no haya pares, por lo que la probabilidad de al menos un par es uno menos el número anterior.

J = .2425
K = 365
.xrK-hKQ = (365 * 364 * ... 365 - n + 2)
+hK*QtJ = (365 + 1 + n * (.2425 - 1))
^+KJQ = (365.2425 ^ n)

isaacg
fuente

5

Python, 179 178 144 143 140 136 135 133

f=.2425
g=365+f
a=lambda n:(n and(365-n)*a(n-1)or 365)/g
b=lambda n:(n<2and f or(367-n)*b(n-1)+a(n-2)*f)/g
p=lambda n:1-a(n-1)-b(n)

p(n)da el resultado. Cambie .2425a fractions.Fraction(97,400)para obtener un resultado exacto.

orlp
fuente

No necesitas un espacio entre 2y and.

isaacg

No se puede poner en 1/para gy se dividen por ella en su lugar?

xnor

@xnor Sí, con el tiempo estas cosas se pierden :) Lo que una vez fue una optimización se vuelve subóptima más tarde.

orlp

podría introducir e=365y reemplazar 365 por e y 367 por e + 2

Willem

@willem Eso no es más corto.

orlp

2

Python 155 153 151 142 140 bytes

d=146097
b=d/400
c=97/d
e=lambda n:n<2and 1-97/d or e(n-1)*(366-n)/b
f=lambda n:n<2and c or f(n-1)*(367-n)/b+e(n-1)*c
a=lambda n:1-e(n)-f(n)

Llame a(n)por el resultado. Para resultados exactos, envuelva den una fracción.

Prueba aquí

Utiliza la misma técnica que aquí , pero con constantes modificadas.

El numero uno
fuente

No necesitas un espacio entre 2y and.

isaacg

Pensé que era 98 (aunque podría haber enloquecido un error de cálculo ...)

Tim

1

80386 código máquina, 43 bytes.

Hexdump del código:

68 75 6e 33 3b 68 5a eb 07 3b 8b c4 49 d9 e8 d9
e8 d8 00 d9 e8 d9 40 04 de ea d8 c9 d9 00 de eb
e2 f3 d8 ca d9 e8 d8 e1 58 58 c3

Partí de la siguiente fórmula (para la probabilidad complementaria):

$\ prod \ limits_ {i = 0} ^ {k-2} (1- \ frac {97 + 400 * i} {d}) * (1- \ frac {303 * (k-1)} {d})$

(aquí d = 366 * 400 - 303está el número de días en 400 años)

Aquí hay un código de C ++ que lo implementa (ya está optimizado un poco):

double it_opt(int k)
{
    double d = 366 * 400 - 303; // number of days in 400 years
    double result = 1; // probability of no coincidences
    const float const1 = float(400 / d);
    const float const2 = float(303 / d);
    double v1 = 1 + const2;
    double v2 = 1;

    for (int i = 0; i < k - 1; ++i)
    {
        v1 -= const1;
        result *= v1;
        v2 -= const2;
    }
    result *= v2;
    return 1 - result;
}

El código está organizado de modo que requiere el número mínimo de constantes, solo dos ( 400 / dy 303 / d). Utilizo el floattipo para representarlos porque ocupa menos espacio (4 bytes por constante). Además, no quería multiplicar const2por k - 1(porque eso requeriría convertir k - 1a float); el código resta const2repetidamente en su lugar.

Aquí está la lista de lenguaje ensamblador:

    ; // fastcall convention - parameter k is in ecx
    ; // result must be returned in st
    push dword ptr 0x3b336e75; // const1 = [esp + 4]
    push dword ptr 0x3b07eb5a; // const2 = [esp]
    mov eax, esp;              // use [eax] instead of [esp] - 1 byte less
    dec ecx;                   // calculate k - 1
    fld1;                      // initiaze result = 1
    fld1;                      // initialize v1
    fadd [eax];
    fld1;                      // initialilze v2
myloop:
    fld dword ptr [eax + 4];
    fsubp st(2), st;            // update v1
    fmul st, st(1);             // update result
    fld dword ptr [eax];
    fsubp st(3), st;            // update v2
    loop myloop;                // loop
    fmul st, st(2);             // update result by v2
    fld1;
    fsub st, st(1);             // complement result
    pop eax;                    // restore stack
    pop eax;                    // restore stack
    ret;                        // return

anatolyg
fuente

(Algo) paradoja del cumpleaños pedante