La búsqueda de su propio número en una caja

Question

100 (o algún número par 2N :-) ) los detenidos se encuentran en la sala A.Están numeradas del 1 al 100.

Uno por uno (de prisionero #1 para el preso #100, en fin), que se desarrollará en una sala B, en el que el 100 cajas (numeradas de 1 a 100) les esperan.Dentro de la (cerrado) casillas de los números de 1 a 100 (los números dentro de las cajas al azar se permutan!).

Una vez dentro de la sala B, cada prisionero llega a abrir 50 cajas (elige la que uno se abre).Si él encuentra el número que le fue asignado a él en uno de estos 50 cajas, el prisionero llega a entrar en una habitación C y todas las cajas se cierran de nuevo antes de que el próximo uno entra a la sala B de la sala A.De lo contrario, todos los reclusos en las salas a, B y C) se mató.

Antes de entrar en la sala B, los presos pueden ponerse de acuerdo sobre una estrategia (algoritmo).No hay manera de comunicarse entre las habitaciones (y ningún mensaje puede ser a la izquierda en la sala B!).

Hay un algoritmo que maximiza la probabilidad de que todos los presos sobrevivir?¿Qué probabilidad hace que el algoritmo de lograr?

Notas:

• Hacer las cosas al azar (lo que usted llama "no estrategia"), de hecho le da una probabilidad de 1/2 para cada preso, pero luego la probabilidad de que todos ellos sobrevivientes de 1/2^100 (que es bastante bajo).Uno se puede hacer mucho mejor!

• Los presos no son permitidos para reordenar las cajas!

• Todos los prisioneros son asesinados la primera vez que un preso no puede encontrar su número. Y no es posible ninguna comunicación.

• Sugerencia:uno puede ahorrar más de 30 presos en promedio, que es mucho más que (50/100) * (50/99) * [...] * 1

Answer 1

Este rompecabezas se explica en http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml y que esa persona hace un trabajo mucho mejor de explicar el problema.

El "todos los prisioneros son asesinados" afirmación es incorrecta.El "usted puede ahorrar 30+, en promedio," también es incorrecto, el artículo dice que el 30% del tiempo que usted puede ahorrar el 100% de los prisioneros.

Answer 2

Me parece una solución de baja tecnología para este tipo de problema es siempre el mejor camino a seguir.

primero debemos hacer algunas suposiciones acerca de la situación

• Los prisioneros no son todos los programadores o los matemáticos
• Ellos no quieren morir
• Los guardias bien armados

Así que con un 0.005% de probabilidad de que van a ver mañana, hay una muy simple y de baja tecnología la solución a este problema. RIOT

todo es cuestión de pérdidas v ganancia potencial, las posibilidades son presos lejos número de los guardias, y el uso de cada uno de los otros como escudos humanos, como son todos los muertos de todos modos si no es así, se puede aumentar las posibilidades de que el poder de un guardia, una vez que tienen su arma hay oportunidad sube, ayudándoles a más potencia más guardias para obtener más potencia de fuego para aumentar aún más allá de la tasa de supervivencia.una vez que los guardias se dan cuenta de lo que está sucediendo, es probable que la ejecución de las colinas y cerrar la prisión, esto le dará a los medios de comunicación, un mano a mano y, a continuación, es una cuestión de derechos humanos.

Answer 3

Implementar un algoritmo de ordenación y ordenar los cuadros de acuerdo a los números dentro de ellos.

Primer preso tipo de 50 cajas, y el segundo prisionero ordena los otros 50 y se funde con la primera.(Tenga en cuenta que el segundo prisionero puede adivinar los valores dentro de los primeros 50 cajas)

Después de la 2ª prisionero, todas las cajas serán ordenados !!!

Todos los demás pueden abrir las cajas que contienen sus números fácilmente luego.

Answer 4

No sé si esto está permitido, pero la mejor aproximación que puedo encontrar es:

EDITAR:Ok, creo que esto hace.Por supuesto, estoy tratando esto como un problema de computación, no creo que ningún prisionero será capaz de realizar esto, aunque es muy sencillo si no.

Encontrar los 50 primeros números primos, vamos a asumir que tenemos de ellos en una matriz llamada de los números primos.

• La primera prissioner entra en la sala B y abre la caja y encuentra el número m.
• Esperar de los números primos[1]^m (que sería 3^m)
• Abra el cuadro 2 y lea el número --> n
• Esperar (de los números primos[2]^n - 1) * los números primos[1]^m, que sería (5^n - 1) * 3^m y el tiempo total que ha estado esperando 3^n * 5^n

Repita.Después de la primera prisionero el tiempo total para él sería:3^m * 5^n * 7^p ...= X

Antes de la segunda prisionero entra en la habitación factorizar X.Usted sabe de antemano de los números primos que se han utilizado para la factorización es trivial.Hacerlo usted obtener m, n, p, etc por lo que el segundo prisionero sabe que cada caja/número de combinación de los anteriores prisionero utilizado.

La probabilidad de que la primera de ellas llegar a todo el mundo muerto es 1/2, la segunda tendrá un 50 / (100 - n) (siendo n el número de intentos de la primera), el tercero tendrá 50 / (100 - n - m) (si n + m = 100, a continuación, todas las posiciones son conocidas) y así sucesivamente.

Obviamente, el siguiente prissioner deben omitir las ya conocidas cajas (a excepción de la última elección si la caja que contiene su número es ya conocido)

No sé qué es exactamente la posibilidad ya que dependes de cómo muchas opciones que tienen que hacer, pero yo diría que es bastante alta.

EDITAR:La relectura, si el prissioner no tiene que parar cuando él obtiene su número, a continuación, la probabilidad de que todo el grupo está muy mejorado, exactamente el 50%.

EDIT2:@OysterD ver de esta manera.Si el primer prisionero puede abrir 50 cajas, a continuación, el segundo, saber si su número está en cualquiera de las cajas.Si es así, entonces él puede abrir otras 49 (y por ello el aprendizaje de la caja/número comination de las 100 cajas) y, finalmente, abrir su uno.Así que si la primera prissioner succeds entonces todo el mundo succeds.Recuerda que cada prisionero proporciona una forma para que los demás sepan exactamente las cajas/número de combinación para cada caja que se abre.

Answer 5

Tal vez no estoy leyendo bien, pero la cuestión parece estar mal construida o la falta de información.

Si se encuentra que el número que se asignado a él en uno de estos 50 casillas, el prisionero llega a pie en una sala C, y todas las cajas están cerradas de nuevo antes de que el próximo uno entra a la sala B de la sala A.De lo contrario, todos los los prisioneros (en las salas a, B y C) se mató.

¿La última frase no significa que todos los prisioneros son asesinados la primera vez que un preso no puede encontrar su número?Si no, ¿qué pasa con los presos que no encuentra su número?

Si no es posible ninguna comunicación, y cada vez que un preso entra en la sala B es siempre en idéntico estado, entonces no hay ninguna posibilidad para una estrategia.

Los presos se podría decir que antes de salir de la sala a que el número de caja que se va a abrir.Pero sin posterior presos saber si han tenido éxito o no (suponiendo que el fracaso de uno no es un fracaso para todos) cuando el siguiente prisionero entra en la sala B, que todavía tienen las mismas probabilidades de recoger su número como el anterior prisionero (1:100).

Si el fracaso de uno es el fracaso para todos, entonces por saber en qué casilla de la anterior presos abierto, y a fuerza de el hecho de que no han sido asesinados, cada una de las sucesivas prisionero podría reducir las probabilidades de escoger el mal caja por caja.es decir,1:100 para el primer prisionero, 1:99 para el segundo, a 1:1 para el último.

Answer 6

Los presos estarían de acuerdo en que el prisionero 1 cajas abiertas 1-50.

Si siguen vivos, están de acuerdo en que la próxima prisionero abre cajas 2-51.(el 2 es arbitraria, pero fácil de recordar esta regla) Sus probabilidades de sobrevivir dado que P1 sobrevivido ahora 50/99.Desea eliminar de la apertura de una caja cuando se sabe que el tipo anterior encuentra su.

No sé si eso es óptima, pero es mucho mejor que el azar.

La probabilidad de sobrevivir que parece

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Answer 7

Creo que ya no es posible ninguna comunicación, la mejor estrategia implicaría

la distribución de la probabilidad de cada uno de los presos tan uniformemente como sea posible

Estoy en el camino correcto o no?

La información disponible para cada prisionero:

• El número de survivied prisioneros, así que si tienes una eficiente caja de escoger el sistema que utiliza el orden a cualquier preso que entra en la sala B, entonces una estrategia es, sin duda posible
• Que los cuadros anteriores de los presos escogidos.Por supuesto, no es posible ninguna comunicación durante la carrera y no sería posible recordar cualquier 100s cuadro de picking de permutación. Pero usted podría utilizar esta información para calcular en un sistema de antes de la carrera comienza.

Mi opinión:

1. Dibujar una tabla de números con 2 columnas, la primera columna contiene el número de la caja (cuadro #1 cuadro#100).Cada prisionero, a continuación, elige el 50 cajas y cualquier cuadro de elegir, se debe poner 1 punto en la fila correspondiente de la segunda columna.
2. Todos los presos, sin embargo, son necesarios para nunca elegir cualquier cuadro de dos veces.Y no puede ser marcado más de 50.Algunos presos pueden tener menos opciones que otros, ya que algunos de cuadro puede ser llenados a 50 marcas de primera.
3. Cuando un preso es trasladado a la sala B de que él/ella abre cualquier casillas ha marcado en.

Answer 8

Si todos los prisioneros son asesinados cuando alguien no puede encontrar su número, a continuación, guardar 100 o 0.No hay manera de salvar a 30 personas.

Answer 9

El mismo concepto.

Aonther tomar:

1. Escriba una lista de los primeros 100 números binarios, que tiene cincuenta 1s y cincuenta 0s.
2. Ordenarlos de menor a mayor.
3. Prisionero #1 obtiene el primer número, el prisionero #2 llega la segunda, preso #3 se presenta la tercera y así sucesivamente...
4. Cada prisionero recuerda su número binario.
5. Cuando el preso es trasladado a la sala B, de que él/ella haga coincidir los dígitos binarios de la cantidad que él recordaba con cada uno de los cuadro, el más alto de bits coincide con el de la izquierda del cuadro, el siguiente de bits más alta se corresponde con el segundo de la izquierda del cuadro de ...el bit más bajo se corresponde con el extremo derecho de la caja.
6. Él/ella abre cualquier cuadros de coincidir con 1 y dejar cerradas las cajas de coincidir con 0.

Este sería minimiza la probabilidad, porque a principios de los presos recibirán dígitos que son diferentes de la de los presos y que tiene un número muy juntos obtendría dígitos juntos.Esto no es garantía de supervivencia, pero si los primeros prisioneros sobreviven, es probable que el más tarde los presos tendrían una mayor probabilidad de sobrevivir así.

No he pensado las cifras exactas y razón de ser, pero esta es una solución rápida que puedo pensar en este momento.

Answer 10

No hay límites de tiempo en la pregunta, entonces, sugiero que los presos deben decidir tomar 1 hora por caja y abrirlos en el orden en que se presentan.Si el segundo preso se le permitió entrar a la habitación después de 2 horas, después de que él sabe que el primer prisionero que se encuentra su propio número en el cuadro 2.Por lo tanto, él sabe para omitir el cuadro 2 en su secuencia y se abre cajas de 1, 3, 4...51 Primera presos probabilidades de perder son 50/100 Dado que el primer prisionero que sobrevivió a continuación, la segunda a los presos la oportunidad de ganar 50/99 Así que la respuesta parece ser ((50 ^51)*49!)/100!que según google hace 2.89*10^-9 el que es casi nula Así que incluso si los prisioneros sabían que las cajas previamente suerte de encontrar su número en no habría ninguna esperanza