PI   laBitácora.net                   Mirror Cd por nevrlndtink1

« PreviousNext »

100 prisioneros y una bombilla

11 Junio 2005

Este es uno de mis acertijos favoritos y lo encontré hace un tiempo en inglés, en una historia de Slashdot que comentaba este enlace de la universidad de Berkeley sobre acertijos usados para pruebas técnicas de selección de personal. Dice así:

“100 presos jóvenes serán encerrados en celdas individuales, sin ventanas y aisladas acústicamente. Hay una sala central con una bombilla que está inicialmente apagada. Cada día el guarda elije a uno de los 100 de una forma totalmente aleatoria (ej: últimas dos cifras de un sorteo de lotería diario, como el de la ONCE) y le lleva a la sala central permitiéndole ver una bombilla y accionar un interruptor para cambiar su estado. También le da la posibilidad de afirmar que los 100 prisioneros han visitado la sala, pero si esa afirmación es falsa, todos morirán por su estupidez. Sin embargo, si de verdad es cierto, como premio todos serán puestos en libertad, indultados de sus penas e incluso inscritos en el MENSA. En caso de no afirmar nada, el preso sería devuelto a su celda antes del fin del día.
Antes de comenzar, los presos son informados de esas reglas y se les deja un tiempo en el patio para que elaboren un plan. ¿qué plan establecerías si fueses uno de los 100 prisioneros?”

NOTA1: Según las reglas expuestas, ningún plan garantizaría el premio de forma segura (ej: si por azar a un prisionero nunca le tocase pasar a la sala, nunca será cierta la afirmación), pero se consideraría un buen plan aquel con una esperanza razonable de triunfar (aunque sean unos cuantos años; ej: 28 años).
NOTA2: Se han encontrado planes mucho mejores que otros (algunos con esperanza menor de 4000 días) pero ninguno se ha demostrado que sea el mejor posible. Tampoco se conoce a ciencia cierta el origen de este acertijo.

También recomiendo este blog: Pequeños Enigmas.

Posted in webs, Internet, Acertijos | Trackback | del.icio.us | Top Of Page

    24 Responses to “100 prisioneros y una bombilla”

  1. Acid Says:

    Como suele hacerse en los blogs de acertijos, no hay que dar la solución, para no romper el misterio y que los demás intenten resolverlo. Esa es la gracia: que cada uno disfrute resolviéndolo.
    Lo que suele hacerse, aparte de decir si ya se ha resuelto es dar muestras de que se conoce la solución. En este caso sería una prueba interesante calcularse la esperanza para el plan que hayas encontrado
    (ej: “encontré un plan con la esperanza de salir en 10001 días”), aunque si te resulta muy complicado o pesado de calcular se pueden dar otro tipo de señales.
    También a veces se van dando pistas muy ligeras, con cuentagotas (especialmente el que propuso el acertijo).

  2. sim0n Says:

    Se me ocurren dos soluciones: una mala y otra muy mala.
    En la muy mala nuestros sufridos prisioneros no iban a vivir para contarlo, pero como solución vale.
    Dividimos el tiempo en ciclos de 100 días, y a cada prisionero le asignamos un día de esos 100 conocido por todos. Si a un recluso se le llama al cuartito su día enciende la luz y si le llevan cualquiera de los 99 días restantes no hace nada.
    Cada vez que alguien es llamado y se encuentra con la luz encendida, apunta el prisionero que tenía asignado el día anterior al que él va, y apaga la luz, así se continúa hasta que uno de los prisioneros tenga en su lista personal los 99 restantes.
    La solución es muy mala porque el número de días necesarios es escandaloso, pero con paciencia y vida infinita, todo llega.

  3. Acid Says:

    La solución que aportas efectivamente no es muy buena en cuanto a esperanza, pero el planteamiento tipo Bingo es ingenioso e interesante. De hecho, con una ligera modificación de ese plan, se puede alcanzar una esperanza muchísimo menor y que ya entraría dentro de las mejores soluciones.
    Me gusta este acertijo (entre otras razones) porque se trata de encontrar algoritmos.

  4. mestebanez Says:

    El problema es de una elegancia absoluta.

    Ofrezco una posible solución:

    *********************
    *********************
    *********************

    La solución que se me ocurrió es parecida a la dada por 3., pero con el refinamiento de que se trasmita la información conocida.
    Si el preso 98 se encuentra la luz encendida el día 34 sabe que el preso 33 ya ha estado allí. Si el preso 98 tuviera que salir también el día 1033, encendería la luz, indicando a su compañero lo que sabe: que el preso 33 ya ha estado por allí. Así se compartiría el conoci
    miento y podría llegarse a adivinar mucho más pronto.

    Calcular la esperanza de días para que consiguieran salir debe ser también complejísimo.

  5. MArtin Says:

    Muchachos no les quiero arruinar este gran acertijo pero es mucho mas probable salir si se arriesgan a elegir sin tener la seguridad. de esa manera con un 50% de seguridad salen al dia. Pero obviamnete esto puede fallar ajjajajajaj

  6. sim0n Says:

    50% ??????????
    No confundamos la cantidad de posibilidades que hay, respecto a acertar y no acertar, con la probabilidad de ganar.
    Un caso muy claro es la loteria, si juegas un boleto pueden pasar que te toque el primer premio o que no, lo cual no significa que las probabilidades de que te toquen sea un 50%, concretamente en el caso de la loteria es de 1/65000, ya que hay 65000 números posibles con la misma probabilidad cada uno de que sea el agraciado.

  7. ACid Says:

    Espero que MArtin lo dijese en broma, los primeros 99 días si alguien dice que está seguro que han pasado los 100 lo que hace es suicidarse y matar a sus compañeros.
    La probabilidad es exactamente 0 esos 99 días. El día número 100 la probabilidad no es cero pero es ridículamente pequeña. Que el segundo día salga uno diferente al primero (99/100), que el tercer día salga uno de los 98 restantes, etc : (99/100) * (98/100) * (97/100) … * (1/100) = 99! / (10^198) = 9,33e-43
    algo más difícil que acertar el gordo de la lotería 9 veces seguidas, o más difícil que acertar la primitiva 6 veces seguidas ó acertar euromillones 5 veces seguidas…
    ¿Cuantos días (ó años) tienen que pasar para que la probabilidad sea un 50%? Según mis cálculos me salen 527 días. Y para que la probabilidad de morir sea un 10% deberían pasar 687 días (pero no se si mis cálculos son válidos: exactos estoy casi convencido que no, pero intenté que fueran muy muy aproximados)
    Para evitar estrategias al azar como esta se podría pedir la demostración de que no estás arriesgando tu vida y la de los demás
    (una demostración es enseñar el plan y mostrar que con ese plan y lo ocurrido, podías hacer la afirmación sin arriesgar)

  8. ACid Says:

    mestebanez,
    me alegro que encontrases la pequeña mejora del plan presentado por Simon (en #2), en el cual la esperanza es muy aceptable. Además, es un plan bastante simple y también es resistente a fallos: a alguien se le puede olvidar apuntar informacion o se le puede olvidar transmitir alguna vez y no pasa nada (salvo un posible retraso).
    El cálculo de la esperanza en este caso es algo más difícil que en otros. Al principio la probabilidad de transmitir es 1/100 (en los primeros 100 días lo típico es que sólo a uno le toque en su día y lo transmita) pero según avanza el tiempo la probabilidad de transmitir superaría el 50% y cerca del final estaría la luz encendida casi siempre de forma que alguien que hubiese visitado poco la habitación podría rápidamente ir captando la información.

    Intentaré calcular la esperanza.

    Pero no se acaba aqui, hay estrategias más simples y otras más eficientes (con esperanza menor).

  9. sympathetic Says:

    en cuanto a la forma de la sala central, se supone que todas estan colocadas alrededor de la sala central que tiene la bombilla y supongo que conectadas cada celda por una puerta hacia la sala central, si las celdas tuvieran una sola puerta, como normalmente son… pues debieron cada uno haber entrado por el aula central y por tanto, todos ya han estado ahì aunque solo fuera para entrar…
    diganme si estoy mal en algo porfa

  10. ACid Says:

    sympathetic, la solución no va por ahí. Este problema no es un “cazabobos”. Como se dice en la NOTA1, ningún plan garantiza el éxito seguro… Así que se supone que la sala central sería como una celda más, con una sola puerta y que el guarda deja pasar sólo para el vigilante que le toque cada día…
    En este problema, el planteamiento que se colocó originalmente era mucho más simple pero se empezaron a dar soluciones truculentas (”las celdas tienen una ventana desde la que se ve la sala central”, “exigen que la sala donde elaboran el plan sea la sala central y así la han visitado todos”, etc…) y el enunciado se amplió (el plan se elabora en el patio, no en una sala, las celdas no tienen ventanas, están aisladas…)

    El enunciado se puede plantear simplemente en un estilo informático: la bombilla es un bit (una varible booleana inicialmente a FALSE) y es la única forma de comunicar 100 procesos. Se ejecuta uno de los 100 al azar en cada iteración. Cada uno dispone de memoria, etc…

  11. mestebanez Says:

    Con el sistema que propuse, me dio por calcular la esperanza(hice un programa informático). Me da en torno a los 85.000 días, más de 200 años. El inconveniente es que para que alguien sepa toda la información debe haber pasado por la sala principal al menos 99 veces. He estado después mirando las otras posibles soluciones(en inglés) y no acaban de convencerme los sistemas.

  12. sympathetic Says:

    si acid, lo se, solo intentaba dar una solucion de 15 minutos.

  13. mario Says:

    Esta solución puede ser una locura, tontería, etc., pero es otra alternativa.
    En el patio hacemos un ensayo con una bombilla (igual que la de la cárcel)y su casquillo correspondiente. La cuestion es medir en cuantas vueltas (y fracción de vuelta) se desenrosca y dividir el numero de vueltas (expresadas en grados de angulo) entre 100. Cuando sean encarcelados, cada preso que llamen girara la bombilla los grados que le corresponda y solo lo hara una vez (aunque lo saquen mas veces solo habrá de girarla una vez). El preso que desenrosque la bombilla sera que el que responda correctamente que todos sus compañeros han pasado por ahi.

    Notas: por supuesto cuanto mas rosca tenga la bombilla mejor (la de mi habitación tiene aproximadamente 600º por lo que tocarían a 6º/preso, a 90º por cada 15 presos).
    Rezar porque la bombilla de la carcel sea igual a la del ensayo. Confiar en la destreza de todos los reos.

    Con este metodo la probabilidad de salir será la mas baja (si todo sale idealmente). Y aunque hubiera algún metodo probabilístico que tuviera la misma probabilidad, me infunde más confianza girar la bombilla que el azar

  14. chato Says:

    pinche acertijo vale madre esta de volada de resolver.
    mejor pongan otro donde si se queme uno la tatema.
    asi ni para que lo ponen lo que deberian de hacer es ##### [censurado]

  15. homero Says:

    Sé que este acertijo lleva mucho tiempo, pero lo encontré tan interesante que me decidí a comentar de todas formas.
    Es muy interesante la solución propuesta por Mestebanez (comentario 4). Voy a hacer una simulación en Excel para estimar el valor esperado de días en la cárcel.
    Por otra parte, yo no descartaría las estrategias probabilísticas, que no aseguran un 100% de superviviencia, pero que se les puede exigir un nivel de seguridad del 99%, o del 99,9%, o el que se desee. Por ejemplo, se puede calcular cuantos días hay que esperar para que con un 99% de probabilidad hayan pasado por la sala los 100 presos, y ese día afirmar que han pasado todos. Usando la ampolleta, se puede alcanzar el mismo nivel de seguridad con menos días: se le da la instrucción a cada prisionero de que la primera vez que entra a la sala (sólo la primera vez) tiene que accionar el switch de la ampolleta (prenderla si está apagada, y vice-versa). El prisionero que entra el primer día, además, tiene instrucciones de dejar la ampolleta prendida, independiente del estado en que la encuentre. De esta forma, se puede asegurar que si la ampolleta está prendida, ha pasado un número impar de prisioneros, por lo que la estrategia sería decir que han pasado todos los prisioneros el primer día después de un número determinado, en el que la ampolleta sea apagada o se encuentre apagada.
    Cuando tengo un poco de tiempo (porque ahora estoy trabajando en el pqrst) voy a comparar los valores esperados para la estrategia “segura” contra la estrategia probabilística que describo. Si la diferencia es mucha, yo creo que sería justificable correr el riesgo…
    PD: El tiempo en que los prisioneros están poniéndose de acuerdo en el patio tienen acceso a Excel para hecer estos cálculos, cierto? :)

  16. homero Says:

    En una primera evaluación, me da que con la estrategia segura, el tiempo esperado para salir de la cárcel es de 80 años aprox… lo que es mucho. De hecho la probabilidad de que en 80 años (sin ni mirar la ampolleta) no haya salido todavía alguien es bajísima; en 10000 réplicas que hice con Excel del experimento NI UNA SOLA VEZ faltaba alguien por salir a los 80 años. Esto significa que es conveniente correr un pequeño riesgo, para salir muchísimo antes de la cárcel. De hecho, basta con esperar SOLO 3 A�?OS para tener una probabilidad de 99,8% (estimada) de que ya hayan pasado todos por la sala de la ampolleta.
    Todavía me queda revisar cómo mejora el tiempo esperado al mirar la ampolleta (y asegurarme de no haber hecho nada incorrecto en Excel).
    Saludos!

  17. Aquiles Says:

    A mi se me ocurre la siguiente solución que creo que es mejor que la del bingo. Como en esta los prisioneros dividen el tiempo en periodos de 100 días. La luz se mantiene apagada a no ser que un prisionero entre dos veces a la habitación, en cuyo caso la enciende y queda en este estado hasta el día 100. El prisionero que entra este día sabe que si la luz está apagada no hubo repetidos, o sea que todos entraron al menos una vez (salvo que él haya entrado dos veces, pero eso él lo sabe) y puede arriesgar con seguridad que todos han entrado. Si la luz se encuentra encendida, la apaga y comienza una nueva ronda de 100 días. Quisiera saber si esta es una solución un poco mejor que la 2 (a mi me parece que sí pero no estoy seguro) y si hay algún argumento fuerte para demostrarlo o demostrar lo contrario. Espero sus respuestas.

  18. anyeta Says:

    yo solamente estaba buscando una imagen que observe hace algunos dias en la naranja mecánica yo tengo el cuadro pero no sé como se llama el artista la verda leí las soluciones y enloquecería con el sólo hecho de estar encerrada dos meses en una celda…

  19. Pep Says:

    Hola, En el planteamiento original el preso que haga LA AFIRMACION tiene que tener una certeza absoluta de lo que dice, lo que excluye todo cálculo probabilístico. Entre ellos establecen que siempre hay que accionar el interruptor para encender o apagar ya que ese bit de información es el único que comparten. Al final quedaran pocos, muy pocos y de la relación entre las veces repetidas que salgan y el estado de la bombilla se puede alcanzar en un momento dado la posibilidad de afirmar de forma contundente que…

  20. rhox Says:

    Yo tengo algunas malas soluciones

    1-Nadie afirme nada y aseguren su supervivencia (jajaja es broma)
    _________________________________________________

    2-Todos la primera vez que pasen dejaran la bombilla apagada.
    Si pasan por 2da vez deberan prenderla, pero si estaba prendida (ademas de saber que alguien ya paso 2 veces) debera voverla a apagar
    Y asi sucesivamente. Uno o varios prisioneros podran hacer deducciones(Los prisioneros más solicitados).
    Aunque seria mucho tiempo
    _________________________________________________

    3-Cada vez que saquen a un prisionero este intentara amotinarse ya que uno de 100 intentos debera funcionar (jajajajajaja)
    _________________________________________________

    4-Todos apagaran la luz la primera vez que pasen, la prenderan en la segunda y nunca más la modificaran.
    Cuando un reo pase por una ‘’n'’ vez seguida viendo la luz prendida (que puden ser en 99 n dias a una cantidad cada vez más probable) entonces sera muy probable que todos hayan pasasdo (entre más sea elveado ‘’n'’ más probable será que acierte)
    __________________________________________________

    5-Los focos cada vez dan menos luz asi que…
    Todos apagaran la luz la primera vez que pasen, la prenderan en la segunda y nunca más la modificaran.
    Entonces cuando vean que la luz es más brillante que antes sabran que han cambiado el foco por desgaste lo que significa que estuvo mucho tiempo sin apagarse.
    Basta con que una persona lo presencie 5 o 6 cambios de foco para que las probabilidades sean muy muy altas de que ya nadie más haya faltado

  21. Albert Says:

    Bonito problema, si señor.

    Asumiendo, como dice ACid, que el problema no es un cazabobos, y no entrando en soluciones de artimaña (por cierto: genial la idea de Mario de girar la bombilla, aunque difícilmente realizable), comienzo por olvidarme de la bombilla y dejarlo todo en manos de la diosa fortuna.

    He hecho un programilla que simula N sorteos de números entre el 1 y el 100, donde N es el número de días que deciden esperar los reos.
    Para cada N de la tabla, he lanzado el programilla 10.000 veces y me han salido los siguientes porcentajes de éxito (éxito = todos los números del 1 al 100 han salido al menos una vez)

    N porcentaje
    200 0%
    400 16%
    450 33%
    500 51%
    550 67%
    600 78%
    650 86%
    700 91%
    750 95%
    800 96,46%
    850 98,10%
    900 98,70%
    950 99,21%
    1000 99,46%

    En la reunión de reos, yo presentaría ésta tabla y propondría a votación el número de días que queremos esperar. Si las celdas son frías y la comida es mala, quizás no se vea muy mal una cifra como 600 días, que da un 78% de posibilidades de éxito. Claro, que si las condiciones no son tan malas, esperar un poco más puede valer la pena, porque hasta los 750 días aproximadamente el porcentaje aumenta considerablemente.

    Si utilizamos la bombilla, no veo otra solución segura que la ya propuesta por mestebanez: trabajar con ciclos de 100 días, numerar a gente y que el reo con el numero i, si se da la casualidad de que salga sorteado el dia i, encienda la luz para transmitírselo al reo del dia siguiente. Cada reo de ésta manera irá elaborando una lista de números que han salido. No solo eso, sino que si un reo cae en un dia i en una casilla que ya tiene en su lista, también encenderá la luz para dar la información al siguiente reo de que el reo i ya ha pasado por la habitación. El primero que complete la lista de 100, afirmará con seguridad que todos han pasado.

    Lo malo de éste método es que el reo que haga la afirmación habrá tenido que pasar por la habitación en dias i con i = 1 hasta 100. Y no solo eso, sino que no se contabilizará su paso por la habitación un determinado día del ciclo hasta que no encuentre la luz encendida. Ni idea de cómo determinar la esperanza matemática de días pasados hasta que el proceso acabe, pero está claro que los reos mueren de viejos. He hecho un programilla que simula el proceso, con un numero de presos variable para ir viendo la progresión de dias necesarios
    Y aquí los resultados, lanzando el programa 10 veces para cada numero de presos diferente. Con 100 presos hay que esperar de promedio más de 150 años.

    presos media dias
    3 21
    5 76
    8 238
    10 387
    15 1098
    20 2114
    30 5067
    50 16417
    60 21161
    100 56152

    Por tanto debemos abandonar el método que nos da la certeza.
    La pregunta ahora es: ¿se podría adoptar éste método y dar la orden a los reos de que anuncien el final aun no habiendo completado todos los números en sus anotaciones? Volvemos a un método probabilístico? Podríamos decirles, por ejemplo: “ir anotando, y si llega un momento en que solo os faltan 2 números, anunciad que ya hemos pasado todos”. He dicho 2 números, pero…¿cuál sería un buen número para poner de tope? ¿Es eso mejor que dejarlo todo en manos de la fortuna, mirar la primera tabla y trabajar con probabilidad más tratable? No sé, intuitivamente creo que lo mejor es ignorar la bombilla, esperar 3 añitos y, casi seguro, salir todos libres.

  22. Argi Says:

    Albert.
    Creo que hay otra estrategia que asegura el éxito al 100% aunque en un número mas elevado (a determinar) de dias.
    Como comenta Acid, no explicaré la solución, solo esta pista:
    * Uno de los 100 presos solo apaga y cuenta
    * Los otros, …., bueno, los otros…actuan en consecuencia

  23. RodolfoRV Says:

    La respuesta correcta y sin perdida de generalidad aparece en el libro de Samuel Karlin (1998) de Introducción a los modelos estocasticos 3era edicion. “An Introdution to stochastic modeling” en la página 22. referencia problema 2.3. a través del cual se busca el valor esperado de una muestra con reemplazo de “N” elementos distintos (los cuales en este caso serian los 100 presos) la formula señala que la variable aleatoria “Sr” representa el tamaño de muestra necesario para obtener “r” distintos elementos de una poblacion de “N” elementos distintos. Sustituyendo los valores en la formula se obtiene que se necesitan:

    519 dias en promedio para que pasen los 100 presos.

    esta solucion solo sera comprendida por matematicos, estadísticos o cualquier persona con conocimientos en probabilidad.

    la proxima respuesta debera ser dada por alguien con conocimiento en simulación.. el cual verifique o contradiga este resultado..Espero respuesta.

  24. JulySIL Says:

    mmm yo sabia q este problema lo habia visto en otro lado y sabia q era de probabilidad… ya busco el libro y lo chequeo. Lo que no entiendo… es porque el posteo 23 de RodolfoRV es a las 3:14 a.m del 22 de marzo y yo toy escribiendo a las 2:33 del 22 de marzo… ademas de que resolvio el problema en el posteo 23… interesante el numero 23…no?

Leave a Reply




Estadísticas
Licencia Creative Commons