Hace un año o así, alguno de mis compañeros de la UAB contó el acertijo que ahora copio. En el blog de Noèlia ya se planteó hace días, pero aún no hay respuesta. Yo le doy vueltas y vueltas... pero nada. Aquí va:
Hay una cárcel con 23 prisioneros. Un día, el guardián les dice lo siguiente: todos los prisioneros serán interrogados, uno por uno, en la sala de interrogatorios. Cada prisionero será interrogado arbitrariamente. En la sala de interrogatorios, hay dos interruptores con las posiciones Encendido (on) y apagado (off). Los prisioneros pueden observar y mover sólo uno de los 2 interruptores o ninguno, durante cada interrogación. El guardián no moverá los interruptores. Todos los prisioneros serán liberados tan pronto como uno de ellos correctamente le diga al guardián que todos los prisioneros han sido interrogados al menos una vez.
Sin embargo, si la afirmación es incorrecta, nunca serán liberados. Aparte del interruptor, no es posible otro tipo de intercambio de información entre los prisioneros. Ellos tienen una hora para trazar una estrategia que les garantice su liberación.
La pregunta sería: ¿Cuál es la estrategia que han de seguir para conseguir ser liberados?.
Nota mía ("yo" soy Lola): ¿El 23 es importante? Digo yo que sí...
Lobo: en el intervalo entre clicar el supuesto blog de Noelia y volver a preguntar porqué abro la página Web de Diego Andrés ya hay cuatro posteados ...y no había uno...paciencia please...Noelia es DiegoAndres y en lugar de un foro tiene una gueb??? socorro!
Si no me equivoco, la probabilidad de que un prisionero sea elegido al azar es del 4,35%... siempre y cuando el guardia elija los prisioneros al azar (que es lo que he entendido).
Los vuelve a interrogar todas las veces que quiera, así que es inútil plantear una estrategia serial o una que cuente sobre un número de ensayos cerrado. Puede que un prisionero tarde semanas en ser interrogado de nuevo. Y puede que otro sea interrogado quince veces seguidas.
Creo que la estrategia mejor, puesto que no hay "coste de respuesta", es que todos los prisioneros empiecen a decir que todos han sido interrogados conforme les interroguen por segunda vez.
Se eligen cuatro prisioneros... se les dice que si ven los dos apagados, que levanten el de encendido. Si ven el de encendido levantado, que levanten el de apagado. Si ven los dos levantados, que bajen el de encendido. Si ven levantado el de apagado, que bajen el de apagado. Se les dice que si ya han manipulado los interruptores, que no lo vuelvan a hacer.
De esta forma el grupo de 23 se asegura que por lo menos cuatro prisioneros distintos notifiquen su paso por el interrogatorio.
Transcurrido este tiempo, los 23 podrán comprobar si el grupo ya ha sido interrogado (esto es, si los interruptores vuelven todos a estar apagados). En tal caso, uno debe arriesgarse y decir que han sido todos interrogados. Lo que no sé es si en este caso la probabilidad de que 23 hayan sido interrogados sabiendo a ciencia cierta que 4 aleatorios han sido interrogados es aceptable... juas.
Bueno, ¿y si el guardia no interroga a todos para que se queden encerrados? :-D
Tampoco sé si la cosa mejoraría asignando una transición de estado a cada prisionero. Por ejemplo, el prisionero 1 se encarga únicamente de pasar del estado 0-0 a 0-1... y el prisionero 2 de pasar del estado 0-1 al estado 1-1...
a) El guardián interrogará a todos, pero al puro azar
b) Los prisioneros no pueden hablar entre ellos y no tienen na de ná. Y el 99% son torpones que no saben qué es eso de "contar el tiempo mentalmente".
c) No creo que haya ninguna estrategia que "garantice" al 100% la liberación
Y creo que la solución pasa por asignar un set de reglas a algunos prisioneros, y confiar en que las ejecuten.
Vaya, podría usarse un prisionero "iniciador", un prisionero que "cambia estados" y finalmente un prisionero "lector", que es quien deberá juzgar si todos han pasado por ahí.
¿Qué ocurre si nadie contesta? (con o sin presencia de su abogado). Al menos cada uno cumplirá su condena ¿no? En caso de error no sale ni pirri manson.
The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
Chewie, yo he encontrado dos, una muy elegante y la otra para mí (a lo bruto) donde el número 23 tiene importancia si tenemos en cuenta que...
No, no la copio,porque doy "enviar" y ya alguien lo copió antes. (esa sensación de estar en el lugar equivocado en el momento equivocado :o)
Oye Lola, me has hecho trampa. Yo pensando que los pobres prisioneros podían no mover ninguno, y resulta que tienen que moverlo, según leo en los comentarios... ¿Cuál de las dos versiones es correcta?
En cualquier caso, espero que estén condenados a cadena perpetua porque van a perder un buen tiempo jugando con los interruptores de las narices...
Por cierto, la estrategia correcta, si de una prisión real estamos hablando, es una lucha en plan inmortales (sólo puede quedar uno) entre los prisioneros. Sólo tienen una hora, vale, pero son unos reos muy fieros. El que quede sabrá inmediatamente si todos han sido llamados o no, y, a pesar de haber matado a al menos un prisionero, será puesto en libertad... ;-)
Pues la verdad, sólo se me ocurren soluciones probabilistas, del tipo: "cuando haya pasado tres veces, la probabilidd de que algún otro no haya pasado será menor de ..."
Si en San Google escribo 23 prisioneros en lugar de 23 prisoners salen muchos links de casos actuales con muertos y toma de rehenes...en los cuales el número 23 es frecuente, muy frecuente.
Por un momento me sentí mal...coincidencia, digamos, estoy en mi cuarto de hora metafísico, sorry.
Pues mi mujer, en menos de 10 minutos, me acaba de dar una solución perfecta al caso ideal en el que no estén obligados amover ningún interruptor, y le sobran posiciones. Y comparando con San Google ha dado perfectamente en el clavo.
Yo, mientras tanto, más despistado que un ocho.
En fin, este acertijo la verdad es que no sabía ni siquiera bien el enunciado, supongo que se ha ido modificando con el boca a boca... En el siguiente, primará el rigor, lo prometo.
Creo que resolví el que está planteado en Inglés; sin embargo, creo que muchos saldrían libres antes por absolución de sus culpas que por el método que pensé.
Aaaargh! Me dejo caer por aquí desde el blog del musolari pa ver que se cuentan los matemáticos locos y me encuentro un acertijo de esos que no te dejan ni trabajá, ni dormí ni nadená hasta que los resuelves. Pues bien, yastá, encontré la solución. Pero como los entrevisten a ritmo de uno por día, más les vale cavar un túnel con una cucharilla de café.
ahhh!!!
por favor!! que alguien postee la solucion!!!
ya hemos dejado dias para pensarlo, pero se ve que tengo las neuronas algo atrofiadas, y no la encuentro.
por favor, algun alma caritativa que me libre de etse peso???
en dos dias me ahorcare de una geodesica de pseudoesfera si no me lo decis...
¿Soy el único que la primera idea que tuvo fue que cada preso, mientras acudía a manipular los interruptores dejara pegado un pequeño moco, con lo cual en cuanto uno llegara y viera 22 moquillos pegados sabía que ya estaban todos? ¿Es eso grave, doctor? Bueno, claro, luego uno se pone a pensar y se olvida lo el moco. Luego, sigue pensando y vuelve a considerarlo: o tiznar la pared al lado del interruptor, o hacer una marca con la uña. Entonces ya coges lapiz y papel y piensas que tontamente tú querrías pensar que no van a tener que pasar por ahí muchas veces, y luego ves que para contar cosas, con dos bits, hay que repetir y entonces... uf. Pues eso, que muchas gracias, Lola, por volvernos locos.
por supuesto, en la idea del contador de mocos, sólo valdría hacerlo la vez primera que se pasa. Que no hay que ser guarros. El que no hubiera puesto el moco nunca que viera 22 pegados sería el que habría de decir: "nos vamos"...
jo... si... que alguien ponga la solución, que yo no la sé :). Pero parece que la versión correcta no es la que he puesto, ¿no? Es la que puse en inglés en el comentario 25...
Sólo tenemos dos interruptores, es decir, dos dígitos binarios. Por tanto sólo podemos contar hasta 4. Afortunadamente la memoria humana da para bastante más, de manera que uno de los prisioneros actuará de "contador" (en el doble sentido, porque tendrá que llevar la cuenta de los presos que han ido pasando, y cuando cuente 22, contarle al guardia que ya han pasado todos). Suponiendo que la posición inicial de los interruptores es "00", una estrategia sería:
_ Cada preso normal (todos excepto el "contador") sólo cambiará los interruptores una vez.
_ Si los encuentra en "00" los pasará a "01".
_ Si "01" a "11"
_ Si "11" a "10".
_ Si encuentra un "10", o ya ha cambiado los interruptores en una ocasión anterior, los deja como están.
_ Cuando entre el "contador" y encuentre un "10" sabrá que han pasado al menos 3 presos distintos, vuelve a poner un "00" y apunta mentalmente un 3.
_ Una vez que el "contador" se haya encontrado 7 veces "10" y 1 vez "01", sabrá con seguridad que los otros 22 presos han pasado por allí.
La solución anterior tiene dos problemas: los presos no tienen la opción de no tocar los interruptores y tampoco saben la posición inicial. Vamos por partes, como dijo Jack el destripador.
Cómo tienen que cambiar por fuerza uno de los dos interruptores, sólo usaran uno para contar (digamos el "A"). El interruptor "B" será un comodín, con lo que sólo se puede contar de uno en uno. La estrategia es:
1) Cada preso normal (todos excepto el "contador") sólo cambiará el interruptor "A" una vez.
2) Si lo encuntra en "0" lo pasa a "1".
3) Si lo encuentra en "1", o ya lo ha tocado anteriormente, manipula el interruptor "B".
4) Cuando el "contador" encuentre un "1" en "A" lo pasará a "0" y contará a un preso.
5) Una vez que haya encontrado 22 veces un "1" en "A" sabrá que los otros 22 presos han pasado.
Como los presos no saben la posición inicial de los interruptores el punto 5) sólo es cierto en el caso de que la primere vez que el "contador" entrara encontrara un "0" en "A". Si había un "1", no tiene manera de saber si lo ha puesto otro preso o estaba ahí desde el principio. No vale esperar a ver un 23º "1" en "A", porque si los 22 ya lo han puesto eso no sucederá nunca. La solución es que los presos normales no cambien el interuptor "A" una vez, sino 2. De esta manera el "contador" tendrá que encontrar un "1" en "A" 44 veces, con lo que estará seguro de que los 22 presos han pasado dos veces, o bien que había un "1" en "A" desde el principio, ha habido 21 presos que han pasado 2 veces y el que queda una sóla vez. En ambos casos está 100% seguro de que todos los presos han pasado por allí.
Cómo al contador lo llaman de media una vez cada 23 entrevistas (si los llaman al azar) tendrán que pasar unas 1000 entrevistas para llegar a la solución: lo más probable es que todos los presos hayan pasado bastantes veces. Y como el guardia no le de ritmillo a las entrevistas, van a chupar más presidio que Jean Valjean.
bien despues de no dejar de pensar en este aceritjo durante muy buen tiempo aqui hay una solucion.
uno de los presos sera el contador, el monitor o como le quieran llamar, los demas unicamente tienen que cumplir con la siguiente labor
Solo usaremos un switch
El primero en pasar debera poner el switch hacia arriba independientemente de como este, de ahi en adelante cada uno que pase debera respetar el switch en la misma posicion y solamente debera bajarlo al pasar la segunda vez, el contador sera el unico que pueda subir nuevamente el switch y asi cada preso cuando sea interrogado por segunda vez o mas y el switch este para arriba lo bajara, y el contador sabra que un preso mas fue entrevistado.
Aunque van a tardar mucho tiempo pues es una manera segura de salir sin fallar.
Saludos.
Enrique Trinchan
P.D. Otra opcion es que e acertijo solo habla de un guardia, entonces la estrategia seria, el primero mata al guardia y todos salen felices.....plop
Solución:
Escojemos un encargado de contar. Definimos 2 Mensajes cada uno con 2 codificaciones: Mensaje A (alguien nuevo ha subido): codificaciones (00, 01), mensaje B (nadie nuevo ha subido): codificaciones (10,11). De forma que al ser interrogados podemos elegir si dejar el mensaje que encontramos o cambiarlo.
El objetivo de cada preso es informar al encargado que ha sido interrogado, para ello si se encuentra el mensaje A (alguien nuevo ha subido) es que alguien ya ha informado antes que el y tendra que esperar a la proxima vez para informar y debe dejar el mensaje A. En cambio si encuentra el mensaje B puede cambiarlo al A y asi informar.
El encargado actua de forma distinta: es el unico que puede borrar el mensaje B (aviso) y ponerlo a A, y cuenta una persona.
Pero no sabemos la pos inicial, si la pos inicial era mensaje B el encargado contara un prisionero que no toca, y cuando cuente 22 (el no se cuanta a si mismo) en realidad habran subido 21.
Para ello cada prisionero debe avisar 2 veces.
Asi pues el encargado debe ontar (21*2)= 42 avisos.
Si la pos inicial es B, de los 42 avisos uno sera falso y por lo tanto un prisionero solo habra avisado una vez (suficiente).
Bien espero que quede claro, hasta la vista
para k la luz del interrogatorio se encienda los dos interruptores tienn k estar en "on"
suponiendo k desde un principio los interruptores se encuentran en la posicion "on" para poder identificar a los presos, el primero de ellos bajaría uno de lso interruptores asta la posicion "off" las luces quedarían apagadas, por lo tanto al guardia no puede reconocer al recluso. si siempre entra el mismo recluso, y suponiendo k sabe contar asta 23, solo tiene k estando un interruptor en "off" cambiar el otro.
Cuando el guardían se aburra de preguntar los libera a todos y también se va él de la carcel porque sólo no se va a quedar.
Solamente hay 23 presos si todos se van eso es lo que quiere el guardian para largarse a disfrutar su navidad.
El gurdian se demorará un día con el interrogatorio son 23 prisioneros y tienen una hora para plantear la estrategia que será descontada de las 24 horas del día es decir tienen 23 horas y contando para que al final de la jornada el antepenúltimo de las preguntas coloque el interruptor en encendido y el último arroje la afirmación correcta para ser liberados.
Isaac, yo pense practicamente lo mismo, pero tiene un fallo ese metodo.En este caso, damos por supuesto que el guardia debera interrogar a cada preso AL MENOS UNA VEZ, porque sino, no habria solucion posible.Pero se puede dar el caso de que alguien no sea interrogado por segunda vez, y en tu solucion hay situaciones en las que el recluso debera esperar a la segunda vez para informar y sabemos que puede que no se de una "segunda vez"( a menos , claro esta que haya infinitas interrogaciones, cosa que dudo mucho xD).Por eso, es una solucion aceptable, probablemente util si esta situacion se diera pero no al 100% correcta para el acertijo.
No se si lo que he dicho tieen sentido por favor opinen :)
como dijeron anteriormente creo que no tiene mucha importancia los interruptores, ya que no se sabe la posicion inicial, y si o si se repiten las posiciones, sin saber cuantas personas pasaron por ahi.
si existe la solucion debe estar en otra parte del relato
Segun mi punto de vista es que se vayan separando los que han sido interrogados de los que no, asi sean interrogados 2 veces la mayoria tarde o temprano faltara un solo por interrogar y despues de que este sea interrogado el que siga le dira al guardia que todos han sido interrogados
demasiado facil.. porq hay 23 prisioneros?? el prisionero numero 23 la clave.. el primero interrogado colocará ambos interruptores en posicion off y cada uno que valla pasando subira o bajara el inerrutor, es decir, el primero colocará los 2 en off despues el segundo subira uno de ellos, el tercero subira el otro interruptor, el cuarto bajará el primer interruptor.. y asi sucesivamente llegandose finalmente se podra observar que los interrutores estaran colocados de manera inversa al que los coloco en priemra posicion..
JAVI, no se supone que entran aleatoriamente?
si es asi, entonces tu teoria falla.
Un prisionero pudo haber entrado varias veces al interrogatorio.
Y uno que otro preso podria quedarse sin entrar al interrogatorio, asi que los presos nunca saldrian, si eso pasa
la cosa es muy simple solo tengo 15 años y lo saque antes que uds si hay 2 interruptores el de on y el de off para aquel que pase 2 veces se dara cuenta que ya pasaron todos por que que estaba el de on y si lo repite lo pasara a off giles entonces ya todos van a saber que pasaron todod
La mayoria de los que comenta aqui tienen down o que ocurre? sólo he leido una cantidad asqueante de comentarios diciendo: " hay hay! es muy complicado ya que no se sabe la posicion inicial de los interruptores, blah, blah, blah..." dejen de lloriquear nenas!! claro que se sabe la posicion inicial, el mismo acertijo lo dice!! "dos interruptores con las POSICIONES (((Encendido)) (on) y ((apagado)) (off). " pfff me duele la cabeza de ver estos comentarios. La respuesta es la siguiente: LEEAN BIEN!!!!
La respuesta es bastante simple. Si hay dos interruptores se divide el arco de su trayectoria en doce. De modo que cada preso, cuando le interrogen sólo la primera vez debe bajar un doceavo el interruptor, de modo que cuando todos hayan sido interrogados uno de los dos interruptores había cubiertos todos los doceavos hasta llegar al otro extremo, quedando completamente encendio o apagado, según el caso, y a uno le faltará un onceavo. Para evitarse el problema de que cuando un prisionero nuevo llegue y al ver que cuando ya haya cruzado la mitad del curso, de modo que ya no se puede saber si es el cuarto o el sexto movimiento, el primer prisionero debe golpear los dos interruptores y doblarlos levemente: si está encendido hacia la derecha, si está apagado hacia la izquierda y completar su primer onceavo (sabrá que es el primero porque cada interruptor estará intacto y completamente encendido y apagado; de modo que sabrán si tienen que apagarlo en encenderlo; doblarlo es en si un movimiento de dirección ya que podemos obligar al interruptor a moverse hacia los lados, no estrictamente hacia arriba o hacia abajo,).
Es una respuesta bruta, pero genial en su simplicidad, nada rebuscado ni ecuación.
La respuesta es sencilla, como en todas las películas mientras el guardia pase a coger otro preso para interrogarlo otro le cogerá la llves de carcel sin que se de cuenta. Mientras el guardia interroga al preso, el que cogió las llaves tendrá el suficiente tiempo para liberarse a si mismo y a los demás.
Hace un año o así, alguno de mis compañeros de la UAB contó el acertijo que ahora copio. En el blog de Noèlia ya se planteó hace días, pero aún no hay respuesta. Yo le doy vueltas y vueltas... pero nada. Aquí va:
| Tweet
