Si hay N personas en una fila, y cada hora mata al azar a una persona con un índice impar, y los sobrevivientes vuelven a indexar, ¿quién tendrá más probabilidades de sobrevivir?

Answer 1

De acuerdo, esta es una pregunta divertida.

¿Y qué hacemos con preguntas divertidas?

Matamos la diversión con un crapton de matemáticas.

Entonces. Algunas anotaciones: si la línea tiene una longitud par, denotamos las probabilidades como:

[matemáticas] f_e (0, N), g_e (0, N), f_e (1, N),…, f_e (N-1, N), g_e (N-1, N) [/ matemáticas]

Y si la línea tiene una longitud impar, entonces denotamos las probabilidades como:

[matemáticas] f_o (0, N), g_o (0, N – 1), f_o (1, N),…, g_o (N-2, N-1), f_o (N-1, N) [/ matemáticas ]

Entonces podemos probar, usando las ecuaciones de la cadena de Markov, que:

[matemáticas] f_e (k, N) = \ frac {1} {N} \ cdot 0 + \ frac {k} {N} \ cdot g_o (k-1, N – 1) + \ frac {N – k – 1} {N} f_o (k, N) [/ matemáticas]

[matemáticas] f_o (k, N) = \ frac {1} {N} \ cdot 0 + \ frac {k} {N} \ cdot g_e (k-1, N) + \ frac {N – k – 1} {N} f_e (k, N – 1) [/ matemáticas]

[matemáticas] g_e (k, N) = \ frac {k + 1} {N} \ cdot f_o (k, N) + \ frac {N – k – 1} {N} g_o (k, N-1) [ /matemáticas]

[matemáticas] g_o (k, N) = \ frac {k + 1} {N + 1} \ cdot f_e (k, N) + \ frac {N – k} {N + 1} g_e (k, N) [ /matemáticas]

(Creo. Si cometí un error, ¡díganme en los comentarios! Gracias).

Ahora podemos hacer dos observaciones:

1. Estas ecuaciones son homogéneas, lo que significa que no tenemos que preocuparnos por las probabilidades totales que suman 1; calcular las probabilidades relativas y luego normalizar es lo suficientemente bueno.
2. [matemáticas] f_e (k, N) = f_o (k, N) = g_e (k – 1, N) = g_o (k – 1, N) = k [/ matemáticas] es una solución correcta.
   (Creo. Otra vez.)

Por lo tanto, la probabilidad de sobrevivir como quinto o cuarto es el doble de la probabilidad de sobrevivir como segundo o tercero, la probabilidad de sobrevivir como séptimo o sexto es tres veces la probabilidad de sobrevivir como segundo o tercero, y así sucesivamente.

De hecho, la probabilidad de supervivencia aumenta linealmente con la posición (que ya ha sido insinuada por las simulaciones).

Se el último chico.

Answer 2

Como ya se escribió, el más probable de sobrevivir será el último. Si el problema se expresa como encontrar la probabilidad exacta de que la persona #k ​​sobreviva, la solución es básicamente simple, pero probablemente demasiado difícil de resolver con n mayor que aproximadamente 100 o mucho menos.

Si el último queda vivo como ganador, la persona que tiene la 2. posición al final gana. O 1-10 posición, si se deja vivir a 10 personas. Para calcular las probabilidades para las posiciones finales, podemos calcular la probabilidad para cada combinación posible de eventos que conducen a ellos y finalmente contar la suma de combinaciones favorables para #k. En la tabla a continuación lo he calculado para 5 personas. Para seis personas, habría tomado 3 tablas y, en general, sumando la persona n + 1, el trabajo de resolución se multiplica por aproximadamente N / 2. Esto parece ser un problema factorial de O (n!).

Answer 3

Algunas de las respuestas existentes dicen que la persona 2 es más probable que sobreviva más tiempo, pero eso ya es falso cuando se usa [matemática] n = 4 [/ matemática].

Para ese caso simple, la persona 2 tiene una probabilidad de 1/4 de sobrevivir hasta el final, y la persona 3 tiene 1/4. La persona 4, sin embargo, tiene una probabilidad de 1/2.

El problema de ser el segundo es que la persona es que si en cualquier momento antes del paso final, se elige a la persona 1 (que tendrá probabilidades cada vez mayores), eventualmente morirá (ya que se convierte en la persona 1 siempre condenada).

En cierto modo, debes evitar convertirte en la persona 1 el mayor tiempo posible. Hasta el último turno, de hecho.

Resolver las probabilidades reales se vuelve un poco complicado, pero vamos a intentarlo.

Primero, calculemos la probabilidad de sobrevivir si estamos en la posición final.

Cuando [math] n [/ math] es par, obviamente no podemos morir. Excelente hasta ahora. Cuando [math] n [/ math] es impar, digamos [math] n = 2m + 1 [/ math], tenemos una probabilidad de [math] \ frac {1} {m + 1} = \ frac {2} {n + 1} [/ math] de morir, dando una probabilidad de [math] \ frac {n-1} {n + 1} [/ math] de sobrevivir. La probabilidad total de sobrevivir a la prueba completa hasta el paso final, comenzando con [matemáticas] n [/ matemáticas], incluso, es entonces:

[matemáticas] \ displaystyle \ frac {n-2} {n} \ frac {n-4} {n-2} \ frac {n-6} {n-4} \ cdots \ frac {2} {4} = \ frac {2} {n} [/ matemáticas]

Si comenzamos en la segunda posición, estamos condenados si alguna vez se selecciona a la persona 1 hasta el turno final. La probabilidad de sobrevivir es igual a:

[matemáticas] \ displaystyle \ left (\ frac {n-2} {n} \ right) ^ 2 \ left (\ frac {n-4} {n-2} \ right) ^ 2 \ cdots \ left (\ frac {2} {4} \ right) ^ 2 = \ frac {2 ^ 2} {n ^ 2} [/ math] que es claramente menor que la probabilidad al comenzar en la posición final.

Para [matemáticas] n = 60 [/ matemáticas], obtenemos una probabilidad de [matemáticas] \ frac {1} {900} [/ matemáticas] de sobrevivir comenzando en la posición 2, pero una probabilidad de [matemáticas] \ frac {1 } {30} [/ math] comenzando en la posición final.

La intuición aquí es que, comenzando en una posición más alta que 2, no podemos evitar llegar a una posición extraña de vez en cuando, pero esas posiciones tienen solo una pequeña probabilidad de ser seleccionadas en el siguiente turno. La posición que necesitamos evitar desesperadamente es la posición 1, ya que la persona allí siempre estará en una posición extraña. De todas las personas que comienzan en posiciones pares, la que tiene más probabilidades de terminar en la posición 1 es la persona que actualmente se encuentra en la posición 2. ¡Incluso sería mejor estar en una posición impar más alta desde el principio!

Answer 4

Si por re-indexado quiere decir que las personas detrás de la persona se mueven en la línea, como el número 22 convirtiéndose en el número 21, la persona en el # 2 sería más probable que sobreviva, porque la única forma de que esa persona sea elegible para morir (convertirse una persona de número impar), la persona en el # 1 debe morir. El tipo en el n. ° 4 puede ser elegible si el n. ° 1 o n. ° 3 es elegido, el n. ° 6 puede ser elegible si el n. ° 1, n. ° 3, n. ° 5 y así sucesivamente, por lo que el n. ° 2 tendrá más probabilidades de sobrevivir.

Si por re-indexado quiere decir que se vuelven a ordenar aleatoriamente, cualquier persona con un número par en la primera selección tendrá más probabilidades de sobrevivir, porque sobreviven a la primera ronda, y el resto es aleatorio.

Answer 5

la pregunta que hizo es el problema de José. Siga los siguientes pasos:

1. si el número es una potencia de 2, se expresará completamente como 2 ^ M

2. si el número no es una potencia de 2, expréselo como 2 ^ M + L;

FINALMENTE LA PERSONA QUE SOBREVIVIRÁ TENDRÁ UN ÍNDICE = (2 ^ M)

Answer 6

Edite después de la hermosa respuesta de Robby Goetschalckx:

TL&DR: Esta es una pregunta inesperadamente agradable y todavía me gustaría ser el segundo en lugar del último.

Primero, me gustaría mantener mi respuesta original como se muestra a continuación en el punto 1 y continuar de manera detallada;

1. Creo que el tipo en la segunda posición (índice 2) sería el tipo más afortunado en este escenario. Tiene un índice uniforme y para que lo maten, deben suceder dos cosas. El tipo en el índice n. ° 1 debe ser asesinado para que tenga un índice impar (2 / N) y luego debe ser asesinado (2 / N-1) para que en general 4 / N (N-1). Sin embargo, las posibilidades empeoran a medida que avanzas en la línea. Por ejemplo, tome al tipo al final de la línea. La paridad del índice del tipo en la enésima posición se cambia entre impares e incluso cada vez que alguien es asesinado. Entonces, dependiendo de la longitud de la línea cada vez, su probabilidad es 2 / N (línea de longitud impar) o 2 / (N-1) (línea de longitud par). Entonces sí .. # 2.
2. Pongamos un nombre a este juego. El nombre de este juego es Everyone Dies (TM), que parece ser la marca registrada del muy entretenido autor de Quora, Dave Consiglio. Entonces no hay sobrevivientes en este juego. Todos finalmente mueren. Sin embargo, algunos más tarde que los demás. Entonces, la pregunta debe reformularse como “¿Quién es el último en morir?” . Si esta fuera la pregunta, entonces sí … curiosamente resulta ser el último hombre, la mayoría de las veces es el último en morir. Así que aprobado por Robby.
3. OK … pero no tan rápido …! No te dejes engañar; Si bien el último tipo tiene muchas más posibilidades de morir el último en comparación con el segundo y el resto, aquí hay un punto muy sutil. Si la pregunta debe reformularse como “¿Quién es el que más sobrevivirá?”, El segundo individuo tiene más posibilidades de morir más tarde que el último y el resto. Lo que significa que el segundo tipo morirá eventualmente como los demás, pero en promedio morirá más tarde que todos en casos individuales uno a uno. En otras palabras, el último morirá con más frecuencia antes que el segundo . En este caso particular, las pruebas de 100K en la línea de 60 personas muestran que en promedio el # 2 morirá 44,500 veces antes del # 60, produciendo el # 60 para obtener 55,500 muertes antes del # 2.

Aquí está el código JS que utilicé para probar varias curiosidades de esta bonita pregunta. Esta es la versión que comprueba quién muere primero entre el segundo y el último. Agradecería que me avisen si hay una falla en esta lógica o debajo del código.

función getFirstToDie (a) {
var k = 0,
f = a [1],
l = a [a.length-1],
i = 0;
while (k! == f && k! == l) {
i = ~~ (Math.random () * a.length);
! (i & 1) && (k = a.splice (i, 1) [0]);
}
volver k;
}

prueba de función (a, n) {
var h = {};
k = 0;
mientras que (n -) {
k = getFirstToDie (a.slice ());
h [k] = ++ h [k] || 1;
}
volver h;
}

var a = Array (60) .fill (). map ((_, i) => i + 1),
h = prueba (a, 100000);
console.log (h)

Answer 7

En general, el que tiene más probabilidades de sobrevivir sería alguien que tenga un índice que es una potencia de 2. Cada vez que se reduce la línea (problema extraño …), los índices de los sobrevivientes se dividen por dos. Desea tener constantemente un índice par, por lo que una potencia de dos es lo mejor. Por ejemplo, 8-> 4-> 2-> 1, por lo que sobrevive durante 4 rondas, frente a un índice de 10-> 5, que sobrevive solo 2.