Usted seleccionar al azar dos números enteros entre 1 y 100. ¿Cuál es la probabilidad de que el número mayor es exactamente dos veces el número menor?

Question

Recientemente tomé un HackerRank prueba para una Ciencia de Datos de posición y me esta pregunta equivocada. Llegué a 1/200. He aquí cómo:

Hay 50 combinaciones que harán de esta verdad. (es decir,{1,2},{2,4},{3,6}...{50,100}). La probabilidad de un número específico elegido es 1/100. Probabilidad de que el conjunto va a ser elegida, (1/100 * 1/100).

Ya hay 50 conjuntos,

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

Estoy, por supuesto, asumiendo que 1 y 100 están incluidos. Pero esta fue la respuesta equivocada. Alguien me puede ayudar a entender mi error?

Answer 1

Tu primer error es que no son 50 los resultados, realmente hay 100 (Edit: Véase el comentario a continuación de aclaración). Esto es debido a que llegar (1,2) y (2,1) son los resultados de los dos separados resultados, pero en cada caso el número más grande es exactamente dos veces el número más pequeño.

Así que el total de posibles maneras de conseguir esta realidad está dado por el conjunto:

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

Que es un listado de 100 posibles resultados.

El número total de resultados posibles es $100 \times 99$

Ya hay 100 números posibles para elegir el primer tiempo y, a continuación, 99 para el segundo, ya que deben ser distintos.

Por lo tanto la respuesta es dada por:

$P = \frac{100}{100 \times 99} = \frac{1}{99}$

Utilizando el mismo argumento, es sencillo demostrar que la probabilidad para el caso más general de la elección de los números de $1, 2, ..., n$ donde $n$ es positiva cuando la cantidad está dada por:

$P = \frac{1}{n-1}$

Answer 2

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

Vamos a comenzar con un programa de fuerza bruta enumeración de (a) la "favorable" en los casos en que un número entero es el doble de la otra y (b) de todos los casos posibles. La respuesta sería entonces su relación. Yo he programado una solución general. Su entrada es un número entero positivo n , y 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 la corrección se basa en el hecho de que $i \ne 2i$ para cualquier número positivo $i$.)

Este programa requiere de $3$ pruebas y hasta el $3$ incrementos para cada iteración del bucle interno. Por lo tanto, se necesitan entre $3n$ $6n$ cálculos cada vez que el bucle interno se realiza, o $3n^2$ $6n^2$total. Eso es $O(n^2)$ rendimiento: OK para la pequeña $n$ como $n=100$, pero terrible una vez $n$ supera $10000$ o así.

Como un hacker, una de las primeras cosas que usted querrá hacer es eliminar el cuadrática rendimiento mediante la simplificación del bucle interno (si es posible). Para este fin, de manera sistemática que ir a través de las líneas en el bucle interno (con números) y tenga en cuenta lo siguiente:

1. La línea 1 se ejecuta todos, pero una vez para cada valor de i y, por tanto, all se incrementa el $n-1$ veces. En consecuencia, para el cálculo de all, el lazo sobre j puede ser reemplazado por el incremento all por n-1.

2. La línea 2 se ejecuta exactamente una vez al $2i \le n$ y no lo contrario. Por lo tanto, puede ser sustituido por el incremento all $1$ siempre $2i \le n$.

3. La línea 3 se ejecuta una vez, siempre i es incluso.

Aquí es el transformado del programa.

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 bucle?

1. La línea 1 es ejecutado $n$ veces. Por lo tanto, all se incrementa en n*(n-1).

2. La línea 2' se ejecuta sólo cuando se $2i \le n$. Una manera de contar esto es $\lfloor n/2\rfloor$ (el mayor entero menor o igual a $n/2$).

3. La línea de 3' sólo se ejecuta incluso para valores de $i$. De nuevo, lo que sucede $\lfloor n/2 \rfloor$ 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: una $O(n^2)$ algoritmo se ha reducido a un $O(1)$ algoritmo (que puede ser considerado como un "cerrado" fórmula para la respuesta).

Por último, hay algunos algebraicas simples transformaciones que podemos hacer por hacer rodar la inicialización (línea 0) en el primer uso de cada variable y la combinación de líneas de 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. Vamos a hacerlo con $n=100$:

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

El resultado por tanto es $1/99$.

Para resumir, un ataque de fuerza bruta algoritmo puede ser transformado de forma sistemática el uso de simple programa de reglas de reescritura en un elegante, elegante, $O(1)$ programa.

Answer 3

Primero de todo, usted es el muestreo sin reemplazo. Por lo tanto, hay 100*99 resultados diferentes, por ejemplo, (1,1) no es un documento válido.

En segundo lugar, no importa el orden. El más grande debe ser exactamente el doble, no el segundo. Por lo tanto, eliminar simétrica pares.

Por lo tanto, 50 (100)*99/2 se encuentran positivo, o 1/99