Selecciona aleatoriamente dos enteros distintos entre 1 y 100. ¿Cuál es la probabilidad de que el número mayor sea exactamente el doble del número menor?

8

Recientemente tomé una prueba de HackerRank para un puesto de Data Science y me equivoqué con esta pregunta. Vine a 1/200. Así es cómo:

Hay 50 combinaciones que lo harán realidad. (es decir, {1,2}, {2,4}, {3,6} ... {50,100}). La probabilidad de que se elija un número específico es 1/100. La probabilidad de que se elija el conjunto específico es (1/100 * 1/100).

Como hay 50 juegos,

P=50*(1/100)*(1/100)=1/200

Por supuesto, supongo que se incluyen 1 y 100. Pero esta fue la respuesta incorrecta. ¿Alguien puede ayudarme a entender mi error?

Jo Bennet
fuente
44
La clave de su error es la palabra "distinto".
Matthew Drury
Ahh !! ¿Entonces debería haber sido 50 * (1/100) * (1/99)?
Jo Bennet
44
Averígualo para una versión más pequeña del problema, como reemplazar "100" por "3". Hazlo mediante una enumeración exhaustiva de todos los pares. Debería ver rápidamente cuál es la respuesta correcta para 100.
whuber

Respuestas:

7

Su primer error es que hay 50 resultados, en realidad hay 100 (Editar: vea el comentario a continuación para obtener una aclaración). Esto se debe a que obtener (1,2) y (2,1) son el resultado de dos resultados separados, pero en cada caso el número mayor es exactamente el doble del número menor.

Entonces, las formas totales posibles de obtener esto en realidad están dadas por el conjunto:

{(1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50)}

Que es una lista de 100 posibles resultados.

El número total de posibles resultados es 100×99

Dado que hay 100 números posibles para elegir la primera vez, y luego 99 para la segunda, ya que deben ser distintos.

Por lo tanto, la respuesta viene dada por:

PAGS=100100×99=199

Usando el mismo argumento, es sencillo demostrar que la probabilidad para el caso más general de elegir números de 1,2,...,norte dónde norte es un número par positivo dado por:

PAGS=1norte-1

Empanada
fuente
1
+1. Pero tenga en cuenta que el OP no cometió un error al contar los resultados: estaba contando pares desordenados, lo que hizo correctamente, mientras que usted cuenta los pares ordenados. (Este enfoque es válido: haynorte/ /2 resultados "favorables" de todos (norte2)=(norte/ /2)(norte-1)resultados, cuya proporción da una respuesta totalmente general.) El problema podría caracterizarse mejor como un error al contar el espacio muestral de todos los números distintos no ordenados.
whuber
6

El "Hacker" en el nombre de la prueba sugiere que intentemos encontrar una solución orientada a la informática.

Comencemos por lo tanto con un programa para la enumeración por fuerza bruta de (a) los casos "favorables" en los que un número entero es dos veces el otro y (b) todos los casos posibles. La respuesta sería su relación. He codificado una solución general. Su entrada es un entero positivo ny su salida es la probabilidad.

n=100
all=favorable=0
for i=1 to n
    for j=1 to n
        if (i != j) all=all+1                  {1}
        if (j == 2*i) favorable = favorable+1  {2}
        if (i == 2*j) favorable = favorable+1  {3}
return(favorable / all)

(La prueba de corrección se basa en el hecho de que yo2yo para cualquier número positivo yo.)

Este programa requiere 3 pruebas y hasta 3incrementos para cada iteración del bucle interno. Por lo tanto, necesita entre3norte y 6 6norte cálculos cada vez que se realiza el bucle interno, o 3norte2 a 6 6norte2en general. Eso esO(norte2) rendimiento: OK para pequeños norte me gusta norte=100pero terrible una vez norte excede 10000 más o menos.

Como hacker, una de las primeras cosas que querrá hacer es eliminar el rendimiento cuadrático simplificando el bucle interno (si es posible). Para este fin, revise sistemáticamente las líneas en el bucle interno (como numeradas) y observe lo siguiente:

  1. La línea 1 se ejecuta todo menos una vez para cada valor de iy, por alllo tanto, se incrementanorte-1veces. En consecuencia, para el cálculo de all, el bucle jpuede reemplazarse incrementando allpor n-1.

  2. La línea 2 se ejecuta exactamente una vez cuando 2yonortey de lo contrario no del todo. Por lo tanto, se puede reemplazar incrementando allpor1 cuando 2yonorte.

  3. La línea 3 se ejecuta una vez que se proporciona ies par.

Aquí está el programa transformado.

n=100
all=favorable=0
for i=1 to n
    all = all + (n-1)                      {1'}
    if (2*i <= n) favorable = favorable+1  {2'}
    if (even(i)) favorable = favorable+1   {3'}
return(favorable / all)

¿Podemos ir más allá y eliminar su ciclo?

  1. La línea 1 'se ejecuta norteveces. Por alllo tanto, se incrementa en n*(n-1).

  2. La línea 2 'se ejecuta solo cuando 2yonorte. Una forma de contar esto esnorte/ /2 (el mayor entero menor o igual que norte/ /2)

  3. La línea 3 'se ejecuta solo para valores pares de yo. De nuevo, eso pasanorte/ /2 veces.

La segunda transformación del programa es:

n=100
all=favorable=0                     {0}
all = all + n * (n-1)               {1''}
favorable = favorable + floor(n/2)  {2''}
favorable = favorable + floor(n/2)  {3''}
return(favorable / all)

Esto ya es un logro tremendo: unO(norte2) algoritmo se ha reducido a un O(1) algoritmo (que puede considerarse una "fórmula cerrada" para la respuesta).

Finalmente, hay algunas transformaciones algebraicas simples que podemos hacer al pasar la inicialización (línea 0) al primer uso de cada variable y combinar las líneas 2 '' y 3 '':

n=100
all = n * (n-1) 
favorable = 2 * floor(n/2) 
return(favorable / all)

En este punto, un humano podría ejecutar el programa. Hagámoslo connorte=100:

all = 100 * (100-1) = 100*99
favorable = 2 * floor(100/2) = 2*50 = 100
favorable/all = 100 / (100*99) = 1/99

La salida por lo tanto es 1/ /99.

Para resumir, un algoritmo de fuerza bruta puede transformarse sistemáticamente usando reglas simples de reescritura de programas en un diseño elegante, elegante, O(1) programa.

whuber
fuente
2

En primer lugar, está tomando muestras sin reemplazo. Por lo tanto, hay 100 * 99 resultados diferentes, por ejemplo (1,1) no es un resultado válido.

En segundo lugar, el orden no importa. El más grande debe ser exactamente dos veces, no el segundo. Por lo tanto, elimine los pares simétricos.

Por lo tanto, 50 de (100) * 99/2 son positivos, o 1/99

HA SALIDO - Anony-Mousse
fuente